#include <bits/stdc++.h>
using namespace std;
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");
#define int long long
const int Max = 5e4 + 1;
void nos()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
}
int n,m;
vector < pair < int , int > > v[Max];
void read()
{
    f>>n>>m;
    int i;
    for(i=1;i<=m;i++)
    {
        int n1,n2,cost;
        f>>n1>>n2>>cost;
        v[n1].push_back({n2,cost});
        //v[n2].push_back({n1,cost});
    }
}
int d[Max];
int Use[Max];
void bellmanford(int nod)
{
    int i;
    for(i=1;i<=n;i++)
        d[i] = INT_MAX;
    d[1] = 0;
    queue < int > usefull;
    bitset < 50005 > is_usefull;
    is_usefull = 0;
    usefull.push(nod);
    is_usefull[1] = 1;
    while(!usefull.empty())
    {
        int nod = usefull.front();
        usefull.pop();
        is_usefull[nod] = 0;
        for(auto vec : v[nod])
        {
            int new_cost = d[nod] + vec.second;
            int new_nod = vec.first;
            if(new_cost < d[new_nod])
            {
                d[new_nod] = new_cost;
                if(!is_usefull[new_nod])
                {
                    is_usefull[new_nod] = 1;
                    usefull.push(new_nod);
                    Use[new_nod] ++;
                    if(Use[new_nod] > n)
                    {
                        //s-a dus dreq
                        g<<"Ciclu negativ!";
                        return;
                    }
                }

            }
        }
    }
    for(i=2;i<=n;i++)
        g<<d[i]<<' ';
}
void solve()
{
    bellmanford(1);
}
void restart()
{

}

int32_t main()
{
    nos();

    read();
    solve();
    restart();

    return 0;
}