#include <bits/stdc++.h>
using namespace std;

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

vector<pair<int,int>> a[50005]; 
long long d[50005];
int viz[50005];
int n, m;

void Djikstra(int p){
    d[p] = 0;
    priority_queue<pair<long long,int>, vector<pair<long long,int>>, greater<pair<long long,int>>> q;
    q.push({0,p});
    while(!q.empty()){
        int x = q.top().second;
        long long dist = q.top().first;
        q.pop();
        if(!viz[x]){
            viz[x] = 1;
            for(auto w : a[x]){
                int y = w.second;
                int cost = w.first;
                if(d[x] + cost < d[y]){
                    d[y] = d[x] + cost;
                    q.push({d[y], y});
                }
            }
        }
    }
}

int main()
{
    fin >> n >> m;
    for(int k = 1; k <= m; k++){
        int i, j, c;
        fin >> i >> j >> c;
        a[i].push_back({c,j});
    }
    for(int i = 1;i <= n; i++){
        d[i] = 1e9;
        viz[i] = 0;
    }

    Djikstra(1);

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

    return 0;
}