#include <iostream>
#include <vector>
#include <bitset>
#include <algorithm>
#include <queue>
#include <fstream>

#define eb emplace_back
#define e emplace
#define ll long long
#define FastIo() ios_base::sync_with_stdio(false), cin.tie(nullptr),cout.tie(nullptr);
const int NMAX = 50005;
using namespace std;
int n,m;
int x,y,w;
vector<pair<int,int>> G[NMAX];
bool bellmanFord(){

    queue<int> Q;
    vector<ll> dist(NMAX,1e18),prec(NMAX),nr(NMAX);
    dist[1] = 0;Q.push(1); nr[1] = 1;
    while(!Q.empty()){
        x = Q.front();Q.pop();
        for(pair<int,int> it:G[x])
            if(dist[it.first]>dist[x] + it.second){
                dist[it.first] = dist[x] + it.second;
                nr[it.first]++;
                Q.push(it.first);
                if(nr[it.first]>n) return 0;
            }
    }
    for(int i=2;i<=n;i++) cout<<dist[i]<<' ';
    return 1;
}

int main(){
    freopen("bellmanford.in","r",stdin);
    freopen("bellmanford.out","w",stdout);
    FastIo();
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        cin>>x>>y>>w;
        G[x].emplace_back(y,w);
    }
    bellmanFord();

    return 0;
}