#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;

int main()
{
    int n,m;
    ifstream f ("bellmanford.in");
    ofstream g ("bellmanford.out");

    f>>n>>m;

    vector<vector<int>>a(n+1);
    vector<vector<int>>b(n+1);

    for (int i=1;i<=m;i++){
        int x,y,z;
        f>>x>>y>>z;
        a[x].push_back(y);
        b[x].push_back(z);
    }

queue<int>q;
q.push(1);

vector<int>c(n+1);
c[1]=0;
for (int i=2; i<=n; i++) c[i]=INT_MAX;

int w=0,v=m*m;

while (q.size()>0){
w++; if (w>v) {g<<"Ciclu negativ!"; return 0;}
int x=q.front();
q.pop();

for (int i=0; i<a[x].size(); i++){
    if ((c[x]+b[x][i])<c[a[x][i]]) {c[a[x][i]]=(c[x]+b[x][i]); q.push(a[x][i]); }
}
}

for (int i=2; i<=n; i++) g<<c[i]<<" ";

return 0;
}