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

#define INF 2e9;

using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
const int MAX_N = 50001;
int viz[MAX_N];

struct t_muchie{
    int nod;
    int cost;
};
int drum[MAX_N];
vector<t_muchie>vecini[MAX_N];
int main()
{
    int n,m;
    fin>>n>>m;
    drum[1] = 0;
    for(int i = 2; i <= n; i++){
        drum[i] = INF;
    }

    for(int i = 1; i <= m; i++){
        int nod1, nod2, cost;
        fin>>nod1>>nod2>>cost;
        t_muchie m ={nod2,cost};
        vecini[nod1].push_back(m);
    }
    //initializam
    priority_queue<pair<int,int>> pq;
    pair<int,int> p = {0,1};
    pq.push(p);
    while(!pq.empty()){
        int nod_curr = pq.top().second;
        pq.pop();
        if(!viz[nod_curr]){
            viz[nod_curr] = 1;
            for(int i = 0; i < vecini[nod_curr].size(); i++){
                int vecin = vecini[nod_curr][i].nod;
                int cost = vecini[nod_curr][i].cost;
                if(drum[vecin] > drum[nod_curr] + cost){
                    drum[vecin] = drum[nod_curr] + cost;
                    pair<int,int> pvecin ={-drum[vecin],vecin};
                    pq.push(pvecin);
                }
            }
        }
    }
    for(int i = 2; i <= n; i++){
        if(drum[i] == INF)
            fout<<0<<" ";
        else
            fout<<drum[i]<<" ";
    }
    return 0;
}