#include <bits/stdc++.h>
#define INF 0x3f3f3f3f

using namespace std;

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

int v[50005];

struct varf
{
    int nod, cost;
    bool operator < (const varf & b) const {
        return cost < b.cost;
    }
};

vector <varf> g[50005];
priority_queue <varf> q;

void dijkstra()
{
    q.push({1, 0});
    v[1] = 0;
    while (!q.empty()) {
        int nod = q.top().nod;
        int cost = q.top().cost;
        q.pop();
        if (v[nod] != cost) continue;
        int n = g[nod].size();
        for (int i = 0; i < n; i ++) {
            int cn = g[nod][i].nod;
            int cc = g[nod][i].cost;
            if (v[cn] > cost + cc) {
                v[cn] = cost + cc;
                q.push({cn, v[cn]});
            }
        }
    }
}

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