#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#define NN 50005
#define MM 250005
using namespace std;

ifstream f ("date.in");
ofstream g ("date.out");

const int oo=( 1 << 30);
int n,m,D[NN];
bool incoada[NN];

struct compara
{
    bool operator() (int x, int y)
        {
            return D[x]>D[y];
        }

};

vector < pair <int,int> > V[NN];
priority_queue < int , vector <int> , compara > q;


int main()
{
    f>>n>>m;
    for (int i=1;i<=m;i++)
    {
        int x,y,c;
        f>>x>>y>>c;
        V[x].push_back(make_pair(y, c));
    }

    for (int i=1;i<=n;i++)
        D[i]=oo;
    D[1]=0;
    q.push(1);
    incoada[1]=true;
    while (!q.empty())
    {
        int nodcur=q.top();
        q.pop();
        incoada[nodcur]=false;

        for(int i=0;i<V[nodcur].size();i++)
      {
          int vecin=V[nodcur][i].first;
          int cost=V[nodcur][i].second;
          if (D[nodcur]+cost<D[vecin])
        {
            D[vecin]=D[nodcur]+cost;
            if (incoada[vecin]==false)
            {
              q.push(vecin);
              incoada[vecin]=true;
            }
        }
      }
    }

    for (int i=2;i<=n;i++)
    {
        if (D[i]!=oo)
            g<<D[i]<<' ';
        else
            g<<"0 ";
    }

    return 0;
}