# include <fstream>
# include <iostream>
# include <cstring>
# include <queue>
using namespace std;
ifstream fi("dijkstra.in");
ofstream fo("dijkstra.out");
typedef struct node
{
    int x,y;
    node *next;
} *nod;
const int nmax=50005;
const int infi=1<<30;
nod S[nmax];
queue <int> Q;
int D[nmax];
int read()
{
    char c[30];
    fi>>c;
    int p=0,k=strlen(c);
    for (int i=0;i<k;++i) p=p*10+c[i]-'0';
    return (p);
}
int main(void)
{
    int n=read(),m=read(),x,y,z;
    for (int i=1;i<=m;++i)
    {
        x=read();y=read();z=read();
        nod p=new node;
        p->x=y;p->y=z;p->next=S[x];S[x]=p;
    }
    for (int i=1;i<=n;++i) D[i]=infi;
    Q.push(1);
    D[1]=0;
    while (!Q.empty())
    {
        int q=Q.front();Q.pop();
        for (nod p=S[q];p;p=p->next)
             if (D[p->x]>D[q]+p->y)
                D[p->x]=D[q]+p->y,Q.push(p->x);
    }
    for (int i=2;i<=n;++i)
        fo<<(D[i]==infi ? 0:D[i])<<" ";
    fo<<"\n";
    fo.close();
    return 0;
}