#include<bits/stdc++.h>
#define in f
#define out g
using namespace std;

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

const int MAXN = 50010;
const int INF = 1 << 29;

vector<pair<int, int>> G[MAXN];
bool visited[MAXN];
int d[MAXN];

int m, n;

void read() {
    in >> n;
    in >> m;

    int x, y, z;

    for(int i = 1; i <= m; i++) {
        in >> x;
        in >> y;
        in >> z;

        G[x].push_back({y, z});
    }

}

void solve() {
    for(int i = 2; i <= n; i++) {
        d[i] = INF;
    }

    auto comparator = [](pair<int, int> a, pair<int, int> b) {
        return a.second > b.second;
    };

    priority_queue<pair<int, int>, vector<pair<int, int> >, decltype(comparator)> q(comparator);

    q.push({1, 0});

    while(q.empty() == false) {
        int vertex = q.top().first;
        int cost = q.top().second;

        out << vertex << endl;
        visited[vertex] = true;
        q.pop();

        for(auto v : G[vertex]) {
            if(visited[v.first] == false) {
                if(cost + v.second < d[v.first]) {
                    d[v.first] = v.second + cost;
                    q.push({v.first, d[v.first]});
                }
            }
        }
    }

    for(int i = 2; i <= n; i++) {
        if(d[i] == INF) {
            out << 0 << " ";
        } else out << d[i] << " ";
    }

}

int main() {
    read();
    solve();
    return 0;
}