#include <fstream>
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
long long inf=20001,Min,m,n,p,k,gf[5000][5000],d[50001],t[50001];
bool sel[50001];
void load()
{int a,b,c;
    f>>n>>m;
    for (int i=1;i<=m;i++)f>>a>>b>>c,gf[a][b]=c;
    for (int i=1;i<=n;i++) d[i]=inf,t[i]=0,sel[i]=false;
}
void dijkstra(int a)
{bool ok=true;long long x[101],j=0;
    d[a]=0;
    while(ok)
    {
        Min=inf;
        for (int i=1;i<=n;i++)
            if (d[i]<Min && !sel[i]) Min=d[i],k=i;
        if (Min==inf) ok=false;
        else
        {
            sel[k]=true;
            for (int i=1;i<=n;i++)
                if (!sel[i] && d[i]>d[k]+gf[k][i] && gf[k][i]!=0) d[i]=gf[k][i]+d[k],t[i]=k,x[j++]=d[i];
        }
    }
    for (int i=2;i<=n;i++) if (d[i]==inf) g<<0; else g<<d[i]<<' ';
}
int main()
{
    load(),dijkstra(1);
    return 0;
}