#include <fstream>
#include <vector>
#include <set>
#define INF (1<<30-1)

using namespace std;

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
int v[50005],dp[50001],n,m;

vector <pair<int,int>>graf[50005];
set <pair<int,int>>dij;
void citire(){
    f>>n>>m;
    for(int i=1;i<=n;i++)
        dp[i]=INF;
    for(int i=1;i<=m;i++){
        int x,y,c;
        f>>x>>y>>c;
        graf[x].push_back(make_pair(y,c));
    }
}

void alg(int s){
    int dmin,k,cost,x;
    dp[s]=0;
    dij.insert(make_pair(0,s));
    while(!dij.empty()){
        dmin=dij.begin()->first;
        k=dij.begin()->second;
        dij.erase(dij.begin());
        v[k]=1;
        for(auto&vecin:graf[k]){
            x=vecin.first;
            cost=vecin.second;
            if(!v[x] && dmin+cost<dp[x]){
                dij.erase(make_pair(dp[x],x));
                dp[x]=dmin+cost;
                dij.insert(make_pair(dp[x],x));
            }
        }
    }
}
void afish(){
    for(int i=2;i<=n;i++)
        g<<(dp[i]!=INF?dp[i]:0)<<" ";
}


int main()
{
    citire();
    alg(1);
    afish();
}