#include <fstream>
using namespace std;
int n,m,t[3][250002],start[50002],viz[50002],d[50002];
void citire()
{
    int a,b,c,i,k=0;
    ifstream fin("dijkstra.in");
    fin>>n>>m;
    for(i=1;i<=m;++i)
    {
        fin>>a>>b>>c;
        k++;
        t[0][k]=b;
        t[1][k]=start[a];
        start[a]=k;
        t[2][k]=c;
    }

}
void rezolv()
{
    ofstream fout("dijkstra.out");
    int inf=1000000000,vmin,i,p,j;
    for(i=1;i<=n;++i)
        d[i]=inf;
    d[1]=0;
    for(i=1;i<=n;++i)
    {
        vmin=inf;
        for(j=1;j<=n;++j)
            if(viz[j]==0&&d[j]<vmin){ vmin=d[j];p=j;}
        viz[p]=1;
        for(j=start[p];j!=0;j=t[1][j])
            if(d[t[0][j]]>d[p]+t[2][j] && viz[t[0][j]]==0)
                d[t[0][j]]=d[p]+t[2][j];
    }
    for(i=2;i<=n;++i)
        if(d[i]!=inf)
            fout<<d[i]<<' ';
        else   fout<<'0'<<' ';
    fout.close();
}
int main()
{
    citire();
    rezolv();
    return 0;
}