#include <bits/stdc++.h>

using namespace std;

struct NOD {
    int pos;
};

int n, m,a,b,d;
int MARE = 1000000000;
int dist[50001];
bool parcurs[50001];
vector<int> v[50001],c[50001];
priority_queue<NOD> pq;

bool operator<(const NOD& a, const NOD& b) {
    return (dist[a.pos] > dist[b.pos]);
}

void djikstra() {
    for (int i = 1; i <= n; ++i) dist[i]=MARE;
    NOD nod = { 1 };
    dist[1] = 0;
    pq.push(nod);

    while (not pq.empty()) {
        nod = pq.top();
        pq.pop();
        int ds=dist[nod.pos], pos = nod.pos, vecin;
        if (parcurs[pos]) continue;
        parcurs[pos] = true;

        for (int i = 0; i < v[pos].size(); ++i) {
            vecin = v[pos][i];
            if (dist[vecin] > ds + c[pos][i] and not parcurs[vecin])
                dist[vecin] = ds + c[pos][i], pq.push({vecin});
        }

    }
}

int main() {
    ifstream in("djikstra.in");
    ofstream out("djikstra.out");

    in >> n >> m;

    for (int i = 0; i < m; ++i) {
        in >> a >> b >> d;
        v[a].push_back(b), c[a].push_back(d);
    }

    djikstra();
    
    for (int i = 2; i <= n; ++i) out << dist[i] << ' ';

    in.close(), out.close();
}