#include <fstream>
#include <iostream>

using namespace std;
const int inf=1<<30;
const int Nmax=5000;
int mat[Nmax][Nmax],v[Nmax], d[Nmax], t[Nmax],m,n;
ofstream out("dijkstra.out");

void dijkstra(int ns)
{
    int nod, i, j, minn=inf,ok=1;
    for(i=1; i<=n; i++)
    {
        d[i]=mat[ns][i];
        t[i]=ns;
    }
    v[ns]=1;
    while(ok==1)
    {
        minn=inf;
        for(i=1; i<=n; i++)
            if(!v[i] && d[i]<minn)
            {
                minn=d[i];
                nod=i;
            }
        v[nod]=1;
        if(minn==inf) ok=0;
        else
        {
            for(i=1; i<=n; i++)
            {
                if(v[i]==0 && d[i]>d[nod]+mat[nod][i])
                {
                    d[i]=d[nod]+mat[nod][i];
                    t[i]=nod;
                }

            }
        }

    }

}

int main()
{

    ifstream in("dijkstra.in");
    in>>n>>m;

    int i,j,a,b,c;
    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();
    dijkstra(1);
    for(i=2; i<=n; i++)
        out<<d[i]<<" ";
//    scoate_drum(3);
    return 0;
}