#include<fstream>
#include <utility>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>
#define oo 20000
#define maxn 50001
using namespace std;
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");
int d[maxn],n,i,m,nrp[maxn];
bool v[maxn];
vector <pair <int , int> > a[250001];
//vector <pair <int , int> >::iterator j;
queue < int > coada;
int main()
{
    f>>n>>m;
    int x,y,c;
    for(i = 1; i <= m; i ++)
    {
        f>>x>>y>>c;
        a[x].push_back(make_pair(y,c));
    }
    memset(d , oo, sizeof(d));
    int p = 1;
    coada.push(1);
    d[1] = 0;
    v[1] = true;
    while(!coada.empty())
    {
        p = coada.front();
        //g<<p<<'\n';
        coada.pop();
        for(int j = 0; j < a[p].size();j ++)
        if(d[a[p][j].first] > d[p] + a[p][j].second)
        {
            d[a[p][j].first] = d[p] + a[p][j].second;
            nrp[a[p][j].first] ++;
            if(v[a[p][j].first] == false)
            {
             coada.push(a[p][j].first);
             v[a[p][j].first] = true;
            }
            if(nrp[a[p][j].first] > n)
                {
                   g<<"Ciclu negativ!";
                   return 0;
                }

        }

    }
    for(i = 2; i <= n; i ++)
        g<<d[i]<<" ";
}