#include <bits/stdc++.h>
#define VMAX 100005
#define INF 2000000000
using namespace std;
ifstream fin ("bellmanford.in");
ofstream fout ("bellmanford.out");


int cost[VMAX];
vector<int> vizitat[VMAX];
vector<pair<int,int>> graf[VMAX];
set<pair<int,int>> coada;

void bellmann(int nod)
{
    coada.insert({0,nod});
    auto it = coada.end();
    pair<int,int> x;
    int cost_partial;
    while(coada.size())
    {
        it=coada.begin();
        x=(*it);
        coada.erase(it);
        if(cost[x.second]<x.first)
            continue;

        for(int i=0;i<graf[x.second].size();i++)
        {
            if(cost[graf[x.second][i].first]>x.first+graf[x.second][i].second)
            {
                if(vizitat[x.second][i]==0)
                {
                    fout<<"Ciclu negativ!!\n";
                    exit(0);
                }
                vizitat[x.second][i]--;
                cost[graf[x.second][i].first]=x.first+graf[x.second][i].second;
                coada.insert({x.first+graf[x.second][i].second,graf[x.second][i].first});
            }
        }
    }
}


int main()
{
    int n,m,i,j,k,t,q,nr,minim,maxim,suma;
    fin>>n>>m;
    for(i=0;i<m;i++)
    {
        fin>>j>>k>>t;
        graf[j].push_back({k,t});
        vizitat[j].push_back(n);
    }

    for(i=1;i<=n;i++)
        cost[i]=INF;

    bellmann(1);
    for(i=2;i<=n;i++)
        fout<<cost[i]<<' ';
    fout<<'\n';


    return 0;
}