#include <bits/stdc++.h>
#define MAXN 50000
#define MAXVAL 100000000

using namespace std;

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

priority_queue <pair<int, int>> q;
vector <pair <int, int>> graf[MAXN + 1];
int dist[MAXN + 1];

int main()
{
    int n, m, i, a, b, c, nod, len, vec;

    fin >> n >> m;

    for(i = 1; i <= m; i ++){
        fin >> a >> b >> c;
        graf[a].push_back(make_pair(b, c));
    }
    for(i = 1; i <= n; i++){
        dist[i] = MAXVAL;
    }

    dist[1] = 0;

    q.push({1, 0});
    while(!q.empty()){
        nod = q.top().first;
        len = -q.top().second;
        q.pop();

        if(len == dist[nod]){
            for(i = 0; i < graf[nod].size(); i++){
                vec = graf[nod][i].first;
                if(dist[nod] + graf[nod][i].second < dist[vec]){
                    dist[vec] = dist[nod] + graf[nod][i].second;
                    q.push(make_pair(vec, -dist[vec]));
                }
            }
        }
    }
    for(i = 2; i <= n; i++){
        if(dist[i] == MAXVAL){
            fout << "0 ";
        }else{
            fout << dist[i] << " ";
        }
    }
    fout << "\n";
    return 0;
}