#include<fstream>
using namespace std;
struct vecin {int y,c; vecin* urm;};
struct nod{int x;nod *urm;};
vecin*LA[50003];
int T[50003], D[50003];
int main()
{
    vecin *p;
    nod *first, *last, *r;
    int N,M,x,y,c;
    ifstream fin("dijkstra.in");
    ofstream fout("dijkstra.out");
    fin>>N>>M;
    for (int i=1;i<=M;i++)
    {
        fin>>x>>y>>c;
        p=new vecin;
        p->y=y;
        p->c=c;
        p->urm=LA[x];
        LA[x]=p;
    }
    first=new nod;
    first->x=1;
    first->urm=0;
    last=first;
    for (int i=1;i<=N;i++)
    {
        D[i]=2000000000;
    }
    D[1]=0;
    while (first!=0)
    {
        x=first->x;
        for (p=LA[x];p!=0;p=p->urm)
        {
            y=p->y;
            c=p->c;
            if(D[y]>c+D[x])
            {
                D[y]=c+D[x];
                r=new nod;
                r->x=y;
                r->urm=0;
                last->urm=r;
                last=r;
            }
        }
        r=first;
        first=first->urm;
        delete r;
    }
    for (int i=2;i<=N;i++)
    {
        if(D[i]==2000000000)fout<<"0 ";
        else fout<<D[i]<<" ";
    }
    fout.close();
    fin.close();
    return 0;
}