#include <stdio.h>
#include <vector>

#define MAx 1000000000

using namespace std;

int n, m, viz[50100], d[50100];
vector<pair< int,int> > l[50100];
FILE*f=fopen("dijkstra.in","r"),*g=fopen("dijkstra.out","w");

void initializare()
{
    for(int i = 2; i <= n; i++)
        d[i] = MAx;
    d[1] = 0;
}

int main ()
{
    int x, y, c;
    fscanf(f,"%d %d",&n,&m);
    for(int i = 1; i <= m; i++)
    {
        fscanf(f,"%d %d %d",&x,&y,&c);
        l[x].push_back(make_pair(y,c));
    }
    initializare();
    int minim = MAx, h;

    for(int i = 1; i <= n; i++)
    {
        minim = MAx;
        for(int j = 1; j <= n; j++)
        {
            if(minim > d[j] && viz[j] == 0)
                minim = d[j], h = j;
        }

        viz[h] = 1;

        for(int j = 0; j < l[h].size(); j++)
        {
            if(d[l[h][j].first] > d[h] + l[h][j].second)
            {
                d[l[h][j].first] = d[h] + l[h][j].second;
            }
        }
    }
    for(int i = 2; i <= n; i++)
        if(d[i] == MAx)
            fprintf(g,"0 ");
        else
            fprintf(g,"%d ",d[i]);
return 0;
}