#include <iostream>
#include <fstream>
#include <bits/stdc++.h>

using namespace std;

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

const int Nmax =  50010;
const int Mmax = 250010;
const long long Valmax = 10000000000;
typedef pair<long long, int> value_pair;

class Compare{
public:
    bool operator()(value_pair a, value_pair b){
        return a.first > b.first;
    }
};

int N,M,a[Mmax],b[Mmax],c[Mmax];
vector<pair<int,int> > v[Nmax];
long long dist[Nmax];
priority_queue<value_pair, vector<value_pair>, Compare> q;


int main()
{
    f>>N>>M;
    for(int i=1;i<=M;i++){
        f>>a[i]>>b[i]>>c[i];
        v[a[i]].push_back({b[i], c[i]});
    }
    memset(dist, 127, sizeof(dist));
    dist[1] = 0;
    bool keep_going = true;
    for(int i=1;i<=N&&keep_going;i++){
        keep_going = false;
        for(int j=1;j<=M;j++)
            if(dist[b[j]] > dist[a[j]] + c[j]){
                dist[b[j]] = dist[a[j]] + c[j];
                keep_going = true;
            }
    }
    for(int i=2;i<=N;i++)
        if(dist[i] > Valmax)
            g<<"0 ";
        else
            g<<dist[i]<<' ';
    return 0;
}