#include <bits/stdc++.h>

#define NMAX 100001
#define INF 1e9

using namespace std;

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

vector<pair<int, int>> G[NMAX];
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> Q;
bitset<NMAX> vis;
int N, M, start, finish;
long long dist[NMAX];

void read() {
    int u, v, cost;

    fin >> N >> M;
    //fin >> start >> finish;

    for (int i = 0 ; i < M ; ++i) {
        fin >> u >> v >> cost;
        G[u].push_back(make_pair(v, cost));
    }

    for(int i = 1 ; i <= N ; ++i)
        dist[i] = INF;
}

void solve() {
    vis[start] = 1;
    dist[start] = 0;
    Q.push(make_pair(0, start));

    while (!Q.empty()) {
        int node = Q.top().second;
        int cost = dist[node];
        vis[node] = 0;
        Q.pop();

        for(vector<pair<int, int>>::iterator it = G[node].begin() ; it != G[node].end() ; ++it) {
            if (dist[node] + it->second >= dist[it->first])
                continue;
            dist[it->first] = dist[node] + it->second;
            if (it->first == finish) {
                fout << dist[finish];
                return;
            }
            if (!vis[it->first]) {
                vis[it->first] = 1;
                Q.push(make_pair(dist[it->first], it->first));
            }
        }
    }
}


int main() {
    read();
    solve();

    for (int i = 2 ; i <= N ; i++) {
        if (dist[i] == INF)
            dist[i] = 0;
        fout << dist[i] << ' ' ;
    }
    return 0;
}