#include <bits/stdc++.h>
using namespace std;
ifstream fin ("dijkstra.in");
ofstream fout ("dijkstra.out");
#define NMAX 50003
#define INF 1e9
vector <pair <int, int> >v [NMAX];
priority_queue <pair <int, int>, vector <pair <int, int> >, greater <pair <int, int> > >pq;
bool viz [NMAX];
int dist [NMAX], n, m, A, B, C, nod, vecin;
int main (){
    fin >> n >> m;
    for (int i = 1; i <= m; i ++){
        fin >> A >> B >> C;
        v [A].push_back ({B, C});
    }
    for (int i = 1; i <= n; i ++)
        dist [i] = INF;
    dist [1] = 0;
    pq.push ({0, 1});
    while (!pq.empty ()){
        nod = pq.top ().second;
        pq.pop ();
        if (viz [nod] == 0){
            for (int i = 0; i < v [nod].size (); i ++){
                vecin = v [nod][i].first;
                if (dist [nod] + v [nod][i].second < dist [vecin]){
                    dist [vecin] = dist [nod] + v [nod][i].second;
                    pq.push ({dist [vecin], vecin});
                }
            }
        }
        viz [nod] = true;
    }
    for (int i = 2; i <= n; i ++){
        if (dist [i] == INF)fout << "0" << " ";
        else fout << dist [i] << " ";
    }
    return 0;
}