#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#define MAXN 50005
#define MAX 2000000000

using namespace std;

typedef pair<int,int>pii;

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

vector<pii>graf[MAXN];
priority_queue<pii,vector<pii>,greater<pii> >heap;
bool viz[MAXN];
int dp[MAXN],n,m;



void Dijsktra(int start){
    for(int i = 1; i <= n; i++)
        dp[i] = MAX;
    heap.push({0,start});
    dp[start] = 0;

    while(heap.size()){
        int nod = heap.top().second;
        heap.pop();
        for(int i = 0; i < graf[nod].size(); i++){
            pii curent = graf[nod][i];
            int vecin = curent.first,cost = curent.second;
            if(dp[nod] + cost < dp[vecin]){
                dp[vecin] = dp[nod] + cost;
                heap.push({dp[vecin],vecin});
            }
        }
    }
    for(int i = 1; i <= n; i++)
        if(dp[i] == MAX)
            dp[i] = 0;
}

int main()
{
    in>>n>>m;
    int x,y,weight;
    for(int i = 1; i <= m; i++){
        in>>x>>y>>weight;
        graf[x].push_back(make_pair(y,weight));
    }
    Dijsktra(1);
    for(int i = 2; i <= n; i++)
        if(dp[i] == MAX)
            dp[i] = 0;
    for(int i = 2; i <= n; i++)
        out<<dp[i]<<" ";
    return 0;
}