#include <iostream>
#include <fstream>
using namespace std;
ifstream in ("dijkstra.in");
ofstream out("dijkstra.out");
const int inf = 1<<30;
const int NMAX = 23170;

int mat[NMAX][NMAX];
int V[NMAX], D[NMAX], T[NMAX];
int n,m;

void dijkstra(int ns)
{
    int i,j,minn,nod,ok;
    for(i=1;i<=n;i++)
    {
        V[i]=0;
        D[i]=mat[ns][i];
        T[i]=ns;
    }
    V[ns]=1;
    D[ns]=0;
    T[ns]=0;
    ok=1;
    while(ok)
    {
        minn=inf;
        for(i=1;i<=n;i++)
            if(V[i]==0)
                if(D[i]<minn)
                {
                    minn=D[i];
                    nod=i;
                }
        if(minn!=inf)
        {
            V[nod]=1;
            for(i=1;i<=n;i++)
                if(V[i]==0)
                    if(D[i]>D[nod]+mat[nod][i])
                    {
                        D[i]=D[nod]+mat[nod][i];
                        T[i]=nod;
                    }
        }
        else ok=0;
    }
}
void drum(int x)
{
    if (T[x])
    {
        drum(T[x]);
        out<<" "<<x;
    }
    else out<<x;
}
int main()
{
    int i,j,a,b,c;

    in>>n>>m;
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            mat[i][j]=inf;
    for(i=1;i<=m;i++)
    {
        in>>a>>b>>c;
        mat[a][b]=c;
    }
    in.close();
    /*
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=n;j++)
            if(mat[i][j]!=inf) out<<mat[i][j]<<" ";
            else out<<0<<" ";
        out<<"\n";
    }
    */
    dijkstra(1);
    for(i=2;i<=n;i++)
        if(D[i]!=inf) out<<D[i]<<" ";
        else out<<0<<" ";
    /*
    out<<"\n";
    for(i=1;i<=n;i++)
        out<<T[i]<<" ";
    out<<"Drumul pana la 2 ";
    drum(2);
    */
    return 0;
}