#include <iostream>
#include <vector>
#include <fstream>
#include <queue>

using namespace std;

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

vector <int> vector_vecini[50001];
vector <int> vecin_cost[50001];
priority_queue<pair<int,int>> dijkstra_heap;
int distanta[50001];
int vizitat[50001];

#define maxim 200001

int main() {

    int n,m,a,b,c,i,k,index;
    f>>n>>m;
    for(i=1;i<=m;i++){
        f>>a>>b>>c;
        vector_vecini[a].push_back(b);
        vecin_cost[a].push_back(c);
    }

    for(i=1;i<=n;i++){
        if(i==1)
            distanta[i] = 0;
        else
            distanta[i]=maxim;
        dijkstra_heap.push(make_pair(-distanta[i], i));
    }

    while(!dijkstra_heap.empty() ){
        pair<int,int> p = dijkstra_heap.top();
        index = p.second;
        dijkstra_heap.pop();
        if(vizitat[index] == 1);
        else{
            vizitat[index] = 1;

            int lim = vector_vecini[index].size();
            for(k=0;k<lim;k++){

                int nod_vecin = vector_vecini[index][k];
                if(distanta[nod_vecin] > (distanta[index] + vecin_cost[index][k])) {
                    distanta[nod_vecin] = distanta[index] + vecin_cost[index][k];
                    dijkstra_heap.push(make_pair(-distanta[nod_vecin], nod_vecin));
                }

            }
        }
    }

    for (i = 2; i <= n; i++) {
        if (distanta[i] == maxim)
            distanta[i] = 0;
        g << distanta[i] << " ";
    }

    return 0;
}