#include <fstream>
#include <vector>
#include <queue>
#include <bitset>
#define f first
#define s second
#define DIM 50005
#define INF 250000000
using namespace std;

int n,m,dist[DIM],ap[DIM];
vector<pair<int,int> > adj[DIM];
bitset<DIM> used;

bool isNegativeCycle() {
    for(int i=2;i<=n;i++)
        dist[i]=INF;
    queue<int> q;
    q.push(1);
    used[1]=true;
    ap[1]++;
    while(!q.empty()) {
        int u=q.front(),v,c;
        for(int i=0;i<adj[u].size();i++) {
            v=adj[u][i].f;
            c=adj[u][i].s;
            if(dist[v]>dist[u]+c) {
                dist[v]=dist[u]+c;
                if(!used[v]&&ap[v]<n) {
                    ap[v]++;
                    used[v]=true;
                    q.push(v);
                }
            }
        }
        used[u]=false;
        q.pop();
    }
    for(int i=1;i<=n;i++)
        for(int j=0;j<adj[i].size();j++)
            if(dist[i]+adj[i][j].s<dist[adj[i][j].f])
                return true;
    return false;
}

int main()
{
    ifstream fin("bellmanford.in");
    ofstream fout("bellmanford.out");
    fin>>n>>m;
    int a,b,c;
    for(int i=1;i<=m;i++) {
        fin>>a>>b>>c;
        adj[a].push_back({b,c});
    }
    if(isNegativeCycle())
        fout<<"Ciclu negativ!";
    else
        for(int i=2;i<=n;i++)
            fout<<dist[i]<<" ";
    return 0;
}