#include <bits/stdc++.h>
using namespace std;

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

vector <pair<int,int>> a[50005];
priority_queue <pair<int,int>> q;
int dp[50005];
int n,m,x,y,c;
bitset <50005> v;

void Dik(int x){
    q.push({0,x});
    dp[x]=0;
    while(!q.empty()){
        x=q.top().second;
        q.pop();
        if(!v[x]){
            v[x]=1;
            for(auto w : a[x]){
                if(!v[w.second])
                    if(dp[x]+w.first<dp[w.second]){
                        dp[w.second]=dp[x]+w.first;
                        q.push({-dp[w.second],w.second});
                    }
            }
        }
    }
}

int main()
{
    int i;
    fin >> n >> m;
    for(i=1;i<=m;i++){
        fin >> x >> y >> c;
        a[x].push_back({c,y});
    }
    for(i=1;i<=n;i++) dp[i]=1e9;
    Dik(1);
    for(i=2;i<=n;i++) fout << dp[i] << " ";
    return 0;
}