#include <bits/stdc++.h>

using namespace std;

string name = "dijkstra"; // dijkstra
ifstream fin(name+".in");
ofstream fout(name+".out");

#if 1
#define cin fin
#define cout fout
#endif

typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;

#define MAX 50001
#define MOD % 666013
#define inf 2000000000
#define tt cout << "* ";
#define m1 {cout << "-1";return 0;}
#define da {cout << "DA";return 0;}
#define nu {cout << "NU";return 0;}
#define afisare(d) {for(auto x : d) cout << x << ' '; cout << '\n';}

const int MAXI = 20001;
using pi = pair<int, int>;

vector<int> d;
vector<pi> g[MAX+1];
int n, m, u, v, c;

void dijkstra(int start){
    priority_queue<pi, vector<pi>, greater<pi>> q;
    d[start] = 0;       // dist pana la nodul curent, nod de inceput = 0
    q.push({0, start}); // costul nodului : nod e 0
    while(!q.empty()){
        int nod = q.top().second;
        q.pop();

        for(pi c : g[nod]){ // c is the next node
            if(d[nod] + c.second < d[c.first]){
                d[c.first] = d[nod] + c.second;
                q.push({d[c.first], c.first});
            }
        }
    }
}

int main(){
    cin >> n >> m;
    while(m){
        cin >> u >> v >> c;
        g[u].push_back({v, c});
        m--;
    }

    d.assign(n+1, MAXI);
    dijkstra(1);

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

    return 0;
}