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

using namespace std;

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

vector<pair<int,int> >v[MAXN];
set<pair<int,int> > stiva;
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);
        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});
            }
        }
    }
}

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++)
        out<<dp[i]<<" ";
    return 0;
}