#include <bits/stdc++.h>

const int MAX_N = 50000;

using namespace std;

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

struct Node {
    int v, cost;
    bool operator < (const Node &other) const {
        return this-> cost > other.cost;
    }
};

int n, m;
int dist[MAX_N + 5];

vector<Node> vecini[MAX_N + 5];

void dijkstra() {
    priority_queue<Node> pq;

    for(int i = 1; i <= n; i++)
        dist[i] = INT_MAX;
    dist[1] = 0;

    pq.push({1, 0});
    while(!pq.empty()) {
        Node u = pq.top();
        pq.pop();

        if(u.cost != dist[u.v])
            continue;

        for(auto v : vecini[u.v])
        if(dist[u.v] + v.cost < dist[v.v]) {
            dist[v.v] = dist[u.v] + v.cost;
            pq.push({v.v, dist[v.v]});
        }
    }
}

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

    dijkstra();

    for(int i = 2; i <= n; i++)
        if(dist[i] != INT_MAX) fout << dist[i] << ' ';
        else fout << 0 << ' ';

    return 0;
}