#include<fstream>
#include<set>
#include<stdlib.h>
#define nmax 50020
#define oo 10000000
using namespace std;

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

int i,j , *A[nmax], mini, i0, s[nmax],d[nmax], n, m  ;
int *B[nmax];
int x,y,dis;

set< pair<int,int> > T;

void dijkstra(int r)
{
    int i;
    for(i = 2; i <= n ;i++)
        d[i] = oo;
    T.insert(make_pair(0,1));
    while(T.size() > 0)
    {
        int nod = (*T.begin()).second;
        int dist_min = (*T.begin()).first;

        T.erase(*T.begin());
        if(s[nod] == 1)
        continue;
        s[nod] = 1;
        for(int i = 1; i <= A[nod][0]; i++)
        {
            int ds = dist_min + B[nod][i];

            if(ds < d[A[nod][i]]  )
            {
                d[ A[nod][i] ] = ds ;
                T.insert(make_pair( d[A[nod][i]], A[nod][i]));
            }
        }

    }

    for(int i = 2; i <= n;i++)
        if(d[i] == oo)
            fout <<"0" <<" ";
            else
        fout <<d[i] <<" ";

}
void read()
{
    int i;
    fin >> n >> m;
    for(i = 1; i <= n ;i++)
    {
        A[i] = (int *) realloc(A[i], sizeof(int));
        A[i][0]= 0 ;
    }
    for(i = 1; i <= m ;i++)
    {
        fin >>x >> y >>dis;
        A[x][0]++;

        A[x] = (int *) realloc(A[x], sizeof(int) * (A[x][0] + 1));
        B[x] =(int *) realloc(B[x], sizeof(int) * (A[x][0] + 1));
        A[x][A[x][0]] = y;
        B[x][A[x][0]] = dis;
      //  fout << x <<A[x][A[x][0]] <<'\n' ;
    }

}
int main()
{
    read();
    dijkstra(1);
    fin.close();
    return 0;;

}