#include <bits/stdc++.h>

using namespace std;

const int N_MAX = 50001;
const int INF = 0x7fffffff;

int n, m;
int dist[N_MAX];
vector <int> graph[N_MAX], costs[N_MAX];
queue <int> q;

void read() {
    ifstream fin("dijkstra.in");

    fin >> n >> m;

    int x, y, z;
    for (int i = 0; i < m; ++i) {
        fin >> x >> y >> z;
        graph[x].emplace_back(y);
        costs[x].emplace_back(z);
    }

    fin.close();
}

void solve() {
    int i, node, son, costcrt, l, sum;

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

    q.push(1);

    while (q.size() > 0) {
        node = q.front();
        q.pop();
        costcrt = dist[node];
        l = graph[node].size();
        for(i = 0; i < l; ++i) {
            son = graph[node][i];
            sum = costcrt + costs[node][i];
            if(dist[son] > sum ) {
                dist[son] = sum;
                q.push(son);
            }
        }
    }
}

void write() {
    ofstream fout("dijkstra.out");

    for (int i = 2; i <= n; ++i) {
        if (dist[i] == INF) {
            dist[i] = 0;
        }

        fout << dist[i] << ' ';
    }

    fout.close();
}

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

    return 0;
}