#include <iostream>
#include <fstream>
#include <vector>
#define DIM 50005
#define INF 1000000000

using namespace std;

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

vector<pair<int, int> > l[DIM];
int v[DIM], d[DIM];
int n, m, nod, vecin, cost, x, y, c, minim;

int main (){
    fin>>n>>m;
    for (int i=1; i<=m; i++){
        fin>>x>>y>>c;
        l[x].push_back( make_pair(y, c) );
    }

    for(int i=1; i<=n; i++)
        d[i] = INF;
    d[1]=0;

    while(1){
        minim = INF;
        for(int i=1; i<=n; i++)
            if (v[i] == 0 && d[i] < minim){
                minim=d[i];
                nod=i;
            }

        if (minim == INF)
            break;

        v[nod] = 1;
        for(int i=0; i < l[nod].size(); i++){
            int vecin=l[nod][i].first;
            int cost =l[nod][i].second;

            if (d[vecin] > d[nod] + cost)
                d[vecin]=d[nod] + cost;
        }
    }

    for(int i=2; i<=n; i++)
        if (d[i] == INF)
            fout<<"0 ";
        else
            fout<<d[i]<<" ";
    return 0;
}