#include <bits/stdc++.h>

using namespace std;

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

/**

g[i] - nodurile vecine lui i
first - nodul 2
second - costul

*/
vector <vector <pair <int, int> > > g;
queue <pair <int, int> > q;
int v[50005];

void dijkstra(int s)
{
    q.push(make_pair(s, 0));
    while (!q.empty()) {
        int currentNode = q.front().first;
        int n = g[currentNode].size();
        for (int i = 0; i < n; i ++) {
            int node = g[currentNode][i].first;
            int cost = q.front().second + g[currentNode][i].second;
            if (v[node] == 0) {
                v[node] = cost;
                q.push(make_pair(node, cost));
            }
            if (v[node] < cost) {
                break;
            }
            else if (v[node] > cost) {
                v[node] = cost;
                q.push(make_pair(node, cost));
            }
        }
        q.pop();
    }
}

int main()
{
    int n, m;
    fin >> n >> m;
    g.resize(n + 1);
    for (int i = 1; i <= m; i ++) {
        int a, b, c;
        fin >> a >> b >> c;
        g[a].push_back(make_pair(b, c));
    }
    dijkstra(1);
    for (int i = 2; i <= n; i ++) {
        fout << v[i] << " ";
    }
    return 0;
}