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

using namespace std;

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

vector<pair<int,int> >v[MAXN];
set<pair<int,int> > stiva;
bool viz[MAXN];
int dp[MAXN],n,m;

void Dijkstra(int sursa){
    for(int i = 1; i <= n; i++)
        dp[i] = MAX;
    dp[sursa] = 0;
    stiva.insert({0,sursa});
    while(!stiva.empty()){
        auto top = stiva.begin();
        auto nod = top->second;
        stiva.erase(top);
        if(!viz[nod]){
            for(auto vecin : v[nod]){
                int nod_curent = vecin.first,weight = vecin.second;
                if(dp[nod] + weight < dp[nod_curent]){
                    stiva.erase({dp[nod],nod_curent});
                    dp[nod_curent] = dp[nod] + weight;
                    stiva.insert({dp[nod_curent],nod_curent});
                }
            }
            viz[nod] = true;
        }
    }
}

int main()
{
    in>>n>>m;
    int x,y,weight;
    for(int i = 1; i <= m; i++){
        in>>x>>y>>weight;
        v[x].push_back(make_pair(y,weight));
    }
    Dijkstra(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;
}