#include <bits/stdc++.h>
#define MAX 50000007
#define N 50007

using namespace std;


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

int n,m;
bool ok;
vector<int>dist(N,MAX);
vector<bool>viz(N,0);
vector <pair<int,int>>a[N];
queue<int> q;

void Citire()
{
    fin >> n >> m ;
    for(int i=1;i<=m;i++)
    {
        int x,y,c;
        fin >> x >> y >> c;
        a[x].push_back( {c,y} );
    }
    fin.close();
}

void Update(int x)
{
    viz[x]=1;
    for(auto y:a[x])
        if( dist[y.second]>dist[x]+y.first )
        {
            dist[y.second]=dist[x]+y.first;
            if(!viz[y.second])
                q.push(y.second);
        }
}

void Dijkstra()
{
    dist[1]=0;
    q.push(1);
    while( !q.empty() )
    {
        int cur=q.front();
        q.pop();
        Update(cur);
    }
//    if( !ok )
//        fout << "Ciclu negativ!";
//    else
        for(int i=2;i<=n;i++)
            if( dist[i]==MAX )fout << "0 ";
            else fout << dist[i] << " ";
}



int main()
{
    Citire();
    Dijkstra();
    return 0;
}