using namespace std;
#include<iostream>
#include<fstream>
#include<vector>
#include<set>

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

#define NMAX 50005

int n, m;
vector<pair<int,int>> v[NMAX];
set<pair<int,int>> s;
bool viz[NMAX];
int d[NMAX];

int main() {
    
    fin >> n >> m;
    for (int i = 1; i<=m; i++) {
        int a, b, c;
        fin >> a >> b >> c;
        v[a].push_back({b, c});
    }
    
    for (int i = 1; i<=n; i++) {
        d[i] = 2e9;
    }
    
    s.insert({0, 1});
    d[1] = 0;
    
    while (!s.empty()) {
        pair<int,int> el = *s.begin();
        s.erase(el);
        int nod = el.second;
        int val = el.first;
        viz[nod] = 1;
        
        for (auto it: v[nod]) {
            int nxt = it.first;
            int cst = it.second;
            
            if (viz[nxt]) continue;
            
            if (val+cst < d[nxt]) {
                s.erase({d[nxt], nxt});
                d[nxt] = val + cst;
                s.insert({d[nxt], nxt});
            }
        }
    }
    
    for (int i = 2; i<=n; i++) {
        fout << d[i] << " ";
    }
    
    return 0;
}