#include <bits/stdc++.h>
#define ff first
#define ss second

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pi;
typedef pair<ll, ll> pll;
typedef pair<ld, ld> pld;
typedef vector<int> vi;
typedef vector< vector<int> > vvi;

const string file = "dijkstra";
const ll INF = 9223372036854775807ll;
const int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1}, inf = 2147483647;

int n, m;
vector< vector<pi> > graph;
vi dist;

signed main()
{
    ifstream fin (file+".in");
    ofstream fout (file+".out");
    fin >> n >> m;
    graph.resize(n);
    dist.resize(n, inf);
    vector<bool> ok(n, false);
    for (int i = 0; i < m; ++i){
        int a, b, c;
        fin >> a >> b >> c;
        --a, --b;
        graph[a].push_back(make_pair(b, c));
    }
    auto comp = [](int a, int b){
        if (dist[a] != dist[b])
            return dist[a] >= dist[b];
        return a >= b;
    };
    priority_queue<int, vi, decltype(comp)> q(comp);
    dist[0] = 0;
    q.push(0);
    while(!q.empty()){
        int nod = q.top();
        q.pop();
        if (ok[nod])
            continue;
        ok[nod] = true;
        for (auto neighbor : graph[nod])
            if (dist[nod]+neighbor.ss < dist[neighbor.ff]){
                dist[neighbor.ff] = dist[nod]+neighbor.ss;
                q.push(neighbor.ff);
            }
    }
    for (int i = 1; i < n; ++i)
        fout << (dist[i] == inf ? 0 : dist[i]) << " ";
    return 0;
}