#include <fstream>

using namespace std;
ifstream in("dijkstra.in");
ofstream out("dijkstra.out");
const int Nmax=20000;
const int inf=999999;
int n,m,mat[20000][20000],v[Nmax],d[Nmax],t[Nmax],nod;
void dijkstra(int ns)
{
        int i,ok,mini=inf;
        for(i=1;i<=n;i++)
        {   d[i]=mat[ns][i];
            t[i]=ns;

        }
        d[ns]=0;
        v[ns]=1;
        ok=0;
        while(ok==0)
        {   mini=inf;
            for(i=1;i<=n;i++)
            {   if(d[i]<mini&&v[i]==0)
                {   mini=d[i];
                    nod=i;

                }

            }

            v[nod]=1;
            if(mini==inf) ok=1;
            else
            for(i=1;i<=n;i++)
            {   if(v[i]==0&&d[i]>mini+mat[nod][i])
                {
                  d[i]=mini+mat[nod][i];
                    t[i]=nod;
                }

            }

        }
}
int main()
{   int i,j,a,b,c;
    in>>n>>m;
    for(i=1;i<=n;i++)
    for(j=1;j<=n;j++)
    if(mat[i][j]==0) mat[i][j]=inf;
    for(i=1;i<=m;i++)
    {      in>>a>>b>>c;
            mat[a][b]=c;


    }



    dijkstra(1);
    for(i=2;i<=n;i++)
    if(d[i]==inf) out<<0<<" ";
    else
    out<<d[i]<<" ";
    return 0;
}