# include <iostream>
# include <fstream>
# include <vector>
# include <queue>
 
#define NMAX 50001
#define INF 123456789
using namespace std;
 
vector<pair<int, int> > adList[NMAX];
queue<pair<int, int> > Q;
int distances[NMAX], visited[NMAX];
int N, M;
 
void dijkstra(){
 
    while(!Q.empty()){
        pair<int, int> node = Q.front();
        Q.pop();
 
        for(int i = 0; i < adList[node.first].size(); i++){
            pair<int, int> neigh = adList[node.first][i];
            if(distances[neigh.first] > distances[node.first] + neigh.second){
                distances[neigh.first] = distances[node.first] + neigh.second;
                Q.push(make_pair(neigh.first, distances[neigh.first]));         
            }
            else{
                if(distances[neigh.first] == 0){
                    distances[neigh.first] = distances[node.first] + neigh.second;
                    Q.push(make_pair(neigh.first, distances[neigh.first])); 
                }
            }
        }
    }
}
 
int main(){
    ifstream f("bellmanford.in");
    ofstream g("bellmanford.out");
 
    int a, b, c;
    f >> N >> M;
    for(int i = 0; i < M; i++){
        f >> a >> b >> c;
        adList[a].push_back(make_pair(b, c));
    }
 
    f.close();
 
    Q.push(make_pair(1, 0));
    dijkstra();
 
    for(int i = 2; i <= N; i++)
        g << distances[i] << " ";
 
    g.close();
    return 0;
}