#include <bits/stdc++.h>

using namespace std;

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

struct edge {
    int to;
    int cost;
};

vector<edge> node[50005];
bool visited[50005];
int dist[50005];

int n,m;
int a,b,c;


int main() {
    fin >> n >> m;
    for (int i = 0; i < m; i++) {
        fin >> a >> b >> c;
        node[a].push_back({b, c});
    }

    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>> > q;
    q.push({0, 1});

    while (!q.empty()) {
        int cost = q.top().first;
        int elem = q.top().second;
        q.pop();
        if (visited[elem]) {
            continue;
        }
        visited[elem] = true;
        dist[elem] = cost;

        for (edge e : node[elem]) {
            if (visited[e.to]) {
                continue;
            }
            q.push({cost + e.cost, e.to});
        }
    }

    for (int i = 2; i <= n; i++) {
        fout << dist[i] << " ";
    }
    return 0;
}