#include <fstream>

using namespace std;

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

int n, m, d[50001], viz[50001], p[50001];

struct muchie
{
    int x, y, c;
}mu[250001];

void citire()
{
    fin>>n>>m;
    for (int i=0; i<m; i++)
        fin>>mu[i].x>>mu[i].y>>mu[i].c;
}

void init()
{
    for (int i=2; i<=n; i++)
        d[i]=100000;
}

void dijkstra()
{
    int i=1, ok;
    p[1]=1;
    do
    {
        ok=1;
        for (int j=0; j<m; j++)
            if (mu[j].x==i && viz[mu[j].y]==0 && d[i]+mu[j].c<d[mu[j].y])
            {
                    d[mu[j].y]=d[i]+mu[j].c;
                    p[mu[j].y]=p[mu[j].x];
            }
        viz[i]=1;
        int mn=0;
        for (int k=2; k<=n; k++)
            if (viz[k]==0)
            {
                ok=0;
                if(mn==0)
                    mn=k;
                else
                    if (d[k]<d[mn])
                        mn=k;
            }
        i=mn;
    }while(ok==0);
}

int main()
{
    citire();
    init();
    dijkstra();
    for (int i=2; i<=n; i++)
        if (p[i]==0)
            fout<<0<<" ";
        else
            fout<<d[i]<<" ";
    return 0;
}