#include <iostream>
#include <queue>
using namespace std;

#define FIN "dijkstra.in"
#define FOUT "dijkstra.out"
#define INF 0x3f3f3f3f
#define MAXN 50000

struct point { int v,c; point *l;} *G[MAXN];
int D[MAXN],n,s;

struct Comp
{
    bool operator ()(const int &a , const int &b) {return D[a]>D[b];}
};

priority_queue <int , vector<int> , Comp> Q;

void read_data()
{
    int m,x,y,c;
    point *p;
    freopen(FIN , "r" , stdin);
    scanf("%d %d" , &n , &m ); s=0;
    while (m--)
    {
        scanf("%d %d %d" , &x , &y , &c);x--;y--;
        p=new point; p->v=y; p->c=c; p->l=G[x]; G[x]=p;
    }
    fclose(stdin);
}

void write_data()
{
    freopen(FOUT , "w" , stdout);
    for(int i=1;i<n;i++)
    {
        printf((i<n-1)?("%d "):("%d\n") , D[i] );
    }
    fclose(stdout);
}

void dijkstra(int s)
{
    memset (D,INF,(n+1)*sizeof(int));D[s]=0;
    Q.push(s);
    while(!Q.empty())
    {
        s = Q.top();Q.pop();
        for(point *p=G[s];p;p=p->l)
        if (D[p->v]>D[s]+p->c)
        {
            D[p->v]=D[s]+p->c;
            Q.push(p->v);
        }
    }
}

int main()
{
    read_data();
    dijkstra(0);
    write_data();
    return 0;
}