#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#define NMAX 100010
#define INF 1000000
using namespace std;

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

vector<int> a[NMAX];
vector<int> c[NMAX];

priority_queue< pair<int, int> > pq;

int n, m;

int d[NMAX], vis[NMAX];


int main() {

    f >> n >> m;
    for (int i = 0; i < m; ++i) {
        int x, y, co;
        f >> x >> y >> co;
        x --;
        y --;
        a[x].push_back(y);
        c[x].push_back(co);
    }

    for (int i = 0; i < n; ++i) {
        d[i] = INF;
    }
    d[0] = 0;
    /*for (int i = 0; i < a[0].size(); ++i) {
        int nodCurent = a[0][i];
        int costCurent = c[0][i];
        d[nodCurent] = costCurent;
    }*/

    pair<int, int> p0(0, 0);
    pq.push(p0);
    for (int i = 0; i < n- 1; ++i) {
        pair<int, int> nodCrt = pq.top();
        pq.pop();
        int index = nodCrt.second;
        int val = nodCrt.first;
        val = - val;
        if (vis[index] != 0) {
            i --;
            continue;
        }
        vis[index] = 1;
        for (int j = 0; j < a[index].size(); ++j) {
            int vecinCrt = a[index][j];
            int costVecinCrt = c[index][j];
            if (costVecinCrt + d[index] < d[vecinCrt] && vis[vecinCrt] == 0) {
                d[vecinCrt] = costVecinCrt + d[index];
                pair<int, int> vecin(-d[vecinCrt], vecinCrt);
                pq.push(vecin);
            }
        }
    }

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

    return 0;
}