#include <fstream>
#include <vector>
#include <cstring>
#include <queue>
#include <bitset>
using namespace std;
ifstream cin("bellmanford.in");
ofstream cout("bellmanford.out");
using pi = pair<int,int>;
const int N = 50009,Inf = 0x3f3f3f3f;
int n,m,a,b,c;
int dist[N];
vector<vector<pi>>G;
bitset<N> in_queue;
int cnt_in_queue[N];
bool negative_cycle;

void BellMan()
{
    memset(dist,Inf,sizeof(dist));
    dist[1] = 0;
    queue<int> q;
    q.push(1);
    in_queue[1] = true;


    while(!q.empty())
    {
        int x = q.front();
        in_queue[x] = false;
        q.pop();

        for(auto i : G[x])
        {
            int y = i.first,
            w = i.second;
            if(dist[y] > dist[x] + w)
            {
                dist[y] = dist[x] + w;
                if(!in_queue[y])
                {
                    if(cnt_in_queue[y] > n)
                        negative_cycle = true;
                    else
                    {
                        q.push(y);
                        cnt_in_queue[y]++;
                        in_queue[y] = true;
                    }
                }
            }
        }
    }

}
int main()
{
    cin>>n>>m;
    G = vector<vector<pi>>(n+1);
    while(m--)
    {
        cin>>a>>b>>c;
        G[a].push_back({b,c});
    }

    BellMan();

    if(negative_cycle)
    {
        cout<<"Ciclu negativ!";
        return 0;
    }

    for(int i = 2; i <= n; ++i)
        cout<<dist[i]<<' ';
    return 0;
}