#include <fstream>

using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
int mnm,ok=0,k,a,b,n,m,i,j,c[250][250],d[5000],tata[50],viz[5000];
int main()
{
    f>>n>>m;
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
            c[i][j]=1000000;
    for(i=1;i<=m;i++)
    {
        f>>a>>b;
        f>>c[a][b];
    }
    for(i=1;i<=n;i++)
    {
        d[i]=c[1][i];
        tata[i]=1;
    }
    viz[1]=1;
    tata[1]=0;
    while(!ok)
    {
        mnm=1000000;
        for(i=1;i<=n;i++)
        {
            if(!viz[i]&&d[i]<mnm)
            {
                mnm=d[i];
                k=i;
            }
        }
        if(mnm!=1000000)
        {
            viz[k]=1;
            for(i=1;i<=n;i++)
            {
                if(!viz[i]&&d[i]>d[k]+c[k][i])
                {
                    d[i]=d[k]+c[k][i];
                    tata[i]=k;
                }
            }
        }
        else
            ok=1;
    }
    for(i=2;i<=n;i++)
        if(d[i]==1000000)
            g<<"0 ";
        else
            g<<d[i]<<" ";
    return 0;
}