#include <fstream>
#include <vector>
#include <queue>
#define NMAX 50000
#define INF 100001 ///???????? CE CAT CUM UNDE FARA CUMMMMMMMMMMMM

using namespace std;

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

int n, m, d[NMAX + 1];
bool ver[NMAX + 1];
vector < pair < int, int > > v[NMAX + 1];

void dijkstra(int s) {
    for (int i = 1; i <= n; i++)
        d[i] = INF;
    priority_queue < pair <int, int> > pq;
    d[s] = 0;
    ver[s] = true;
    pq.push({0, s});
    while(!pq.empty()) {
        pair<int, int> f = pq.top();
        int cnc = f.first;
        int nc = f.second;
        pq.pop();
        for (int j = 0; j < v[nc].size(); j++) {
            int nv = v[nc][j].second;
            int cnv = v[nc][j].first;
            if (!ver[nv] && cnv + d[nc] < d[nv]) {
                d[nv] = cnv + d[nc];
                ver[nv] = true;
                pq.push({-d[nv], nv});
            }
        }
    }
}

int main()
{
    fin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int x, y, c;
        fin >> x >> y >> c;
        v[x].push_back({c, y});
    }
    dijkstra(1);
    for (int i = 2; i <= n; i++)
        fout << d[i] << ' ';
    return 0;
}