#include <fstream>
#define nmax 50002
#define mmax 250002
#define inf 2000000000000
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
struct m
{
    int x,y,c;
}G[mmax];
long long D[nmax],x,y,c,n,m,ok,i;
int main()
{
    f>>n>>m;
    for(i=1;i<=m;i++)
    {
        f>>x>>y>>c;
        G[i].x=x;
        G[i].y=y;
        G[i].c=c;
        if(x==1)
            D[y]=c;
    }
    for(i=2;i<=n;i++)
        if(D[i]==0)
        D[i]=inf;
    while(ok==0)
    {
        ok=1;
        for(i=1;i<=m;i++)
            if(D[G[i].y]>D[G[i].x]+G[i].c)
                {
                D[G[i].y]=D[G[i].x]+G[i].c;
            ok=0;
    }
}
for(i=2;i<=n;i++)
    if(D[i]!=inf)
    g<<D[i]<<" ";
else
    g<<0<<" ";
return 0;
}