#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#define NMAX 50005
#include <cstring>

using namespace std;

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

struct Servus{
    int nod,cost;
};
int n,m;
vector<Servus> v[NMAX];
queue<int> q;
int ap[NMAX],dist[NMAX];
void bellmanford(int nod)
{
    memset(dist,0x3f3f3f3f,sizeof dist);
    ap[nod]++;
    dist[nod]=0;
    q.push(nod);
    int ok=0;
    while(q.empty()==false&&ok==0){
        int fata=q.front();
        q.pop();
        for(auto i:v[fata]){
            if(ap[i.nod]<n-1){
                if(dist[fata]+i.cost<dist[i.nod]){
                    dist[i.nod]=dist[fata]+i.cost;
                    q.push(i.nod);
                }
            }
            else
                ok=1;
        }
    }
    if(ok==0){
        for(int i=2;i<=n;++i)
            cout<<dist[i]<<" ";
    }
    else
        cout<<"Ciclu negativ!";
}
int main()
{
    int x;
    Servus y;
    in>>n>>m;
    for(int i=1;i<=m;++i){
        in>>x>>y.nod>>y.cost;
        v[x].push_back({y.nod,y.cost});
    }
    for(int i=1;i<=n;++i){
        cout<<i<<": "<<endl;
        for(auto j:v[i]){
            cout<<j.nod<<" "<<j.cost<<endl;
        }
    }
    bellmanford(1);
    return 0;
}