#include<bits/stdc++.h>
 
#define INF 50000000
 
using namespace std;
 
 
set<pair<int, int>> q;
int viz[50005];
int d[50005];
vector<pair<int, int> >v[50005];
 
 
int main()
{
    FILE *fin = fopen("dijkstra.in", "r");
    FILE *fout = fopen("dijkstra.out", "w");
 
    int n, m, x, y, c;
 
    fscanf(fin, "%d %d", &n, &m);
 
    for(int i = 1; i < n; ++i)
        d[i] = INF;
    for(int i = 0; i < m; ++i) {
        fscanf(fin, "%d %d %d", &x, &y, &c);
        --x; --y;
 
        v[x].push_back(make_pair(y, c));
    }
 
    q.insert(make_pair(0, 0));
    while(!q.empty()) {
        int x = (*q.begin()).first;
        int j = (*q.begin()).second;
        q.erase(*q.begin());
        for(int i = 0; i < v[j].size(); ++i)
            if(x + v[j][i].second < d[v[j][i].first]) {
                d[v[j][i].first] = x + v[j][i].second;
                q.insert(make_pair( d[v[j][i].first], v[j][i].first));
            }
    }
 
    for(int i = 1; i < n; ++i) {
        if(d[i] == INF)
            d[i] = 0;
        fprintf(fout, "%d ", d[i]);
    }
 
}