#include <fstream>
#define NMAX 50005
#define INF 100000000
#include <vector>

using namespace std;
ifstream fin ("dijkstra.in");
ofstream fout("dijkstra.out");
struct arce {int y,c;} arc;
vector <arce> g[NMAX];

int Cmin[NMAX],Prec[NMAX],co;
bool M[NMAX];
int main()
{
    int n,m,i,x,cn,vfmin,mini;
    fin>>n>>m;
    for(i=1;i<=m;i++)
    {
        fin>>x>>arc.y>>arc.c;
        g[x].push_back(arc);
    }
    for(i=0;i<g[1].size();i++)
        Cmin[g[1][i].y]=g[1][i].c;
    for(i=2;i<=n;i++)
        if(!Cmin[i]) Cmin[i]=INF;
    for(i=2;i<=n;i++)
        Prec[i]=1;
    M[1]=1;
    cn=n-1;
    while(cn--)
    {
        mini=INF;
        for(i=2;i<=n;i++)
            if(Cmin[i]<mini && !M[i])
            {
                mini=Cmin[i];
                vfmin=i;
            }
        M[vfmin]=1;
        for(i=0;i<g[vfmin].size();i++)
            if(!M[g[vfmin][i].y]  && Cmin[g[vfmin][i].y]> Cmin[vfmin]+ g[vfmin][i].c)
            {
                Cmin[g[vfmin][i].y]= Cmin[vfmin]+ g[vfmin][i].c;
                Prec[g[vfmin][i].y]=vfmin;
            }
    }
    for(i=2;i<=n;i++)
        fout<<Cmin[i]<<" ";
    return 0;
}