#include <bits/stdc++.h>

using namespace std;

vector <int > DISTANTA(50000);
vector <pair <int, int > > ADJACENT[50000];
priority_queue <pair <int, int> , vector <pair <int, int> >, greater <pair <int, int > > > Q;

void addEdge(int u, int v, int cost){
    ADJACENT[u].push_back(make_pair(v, cost));
}

void dijsktra(int start){
    Q.push(make_pair(0, start));
    DISTANTA[start] = 0;

    while(!Q.empty()){
        int cr = Q.top().second;
        int cost = Q.top().first;
        Q.pop();

        for(auto it: ADJACENT[cr]){
            if(DISTANTA[cr] + it.second < DISTANTA[it.first]){
                DISTANTA[it.first] = DISTANTA[cr] + it.second;
                Q.push(make_pair(DISTANTA[it.first], it.first));
            }
        }
    }
}

int main()
{
    ifstream fin("dijkstra.in");
    int noduri, muchii;

    fin >> noduri >> muchii;

    for(int i = 1; i <= muchii; i++){
        int x, y, cost;
        fin >> x >> y >> cost;
        addEdge(x, y, cost);
    }

    for(int i = 1; i <= noduri; i++){
        DISTANTA[i] = 1e9;
    }

    dijsktra(1);

    ofstream fout("dijkstra.out");
    for(int i = 2; i <= noduri; i++){
        if(DISTANTA[i] == 1e9)
            DISTANTA[i] = 0;
        fout << DISTANTA[i] << " ";
    }

    return 0;
}