//
//  main.cpp
//  C++ - teste
//
//  Created by Filip Cuciuc on 03/02/2020.
//  Copyright © 2020 Filip Cuciuc. All rights reserved.
//

//#include <iostream>
#include <stdio.h>
#include <fstream>
#include <algorithm>
#include <vector>
#include <queue>
#include <math.h>
#include <map>
#include <string>
#include <cctype>
//#include "MED.h"
using namespace std;
//using namespace std::chrono;

ifstream cin("dijkstra.in");
ofstream cout("dijkstra.out");

class cmp {
public:
    bool operator()(pair<int, int> a, pair<int, int> b) {
        return a.second > b.second;
    }
};

const int MAX = 5 * 1e4 + 5;
const int INF = 20001;
int n, m;
int updated[MAX], dist[MAX];
vector <pair <int, int> > mat[MAX];
priority_queue <pair < int, int >, vector < pair < int, int > >, cmp> q;



void read() {
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int A, B, C;
        cin >> A >> B >> C;
        mat[A].push_back({B, C});
    }
}


void solve() {
    read();

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

    q.push({1, 0});
    while (!q.empty()) {
        int now = q.top().first;
        int d = q.top().second;
        q.pop();

        if (updated[now])
            continue;

        updated[now] = 1;
        dist[now] = min(dist[now], d);

        for (auto& x : mat[now]) {
            if (!updated[x.first]) {
                q.push({x.first, x.second + d});
            }
        }
    }

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

}

int main() {

    solve();

    return 0;
}