#include<iostream>
#include<fstream>
#include<iostream>
#include<vector>
using namespace std;
struct muchie{
    int x, y, c;
};

int n, m;
bool cn=false;
muchie mu[250001];
ofstream g("bellmanford.out");
void read(){
    ifstream f("bellmanford.in");
    f>>n>>m;
    for(int i=0;i<m;i++)
        f>>mu[i].x>>mu[i].y>>mu[i].c;
}
vector<int> dist;
vector<int> predecessor;
void bellmanFord(int nod){
    dist.resize(n+1, 1001);
    predecessor.resize(n+1, 0);
    dist[nod]=0;
    for(int i=1;i<n;i++)
        for(int j=0;j<m;j++)
            if(dist[mu[j].x] + mu[j].c < dist[mu[j].y])
                dist[mu[j].y]=dist[mu[j].x]+mu[j].c,
                predecessor[mu[j].y]=mu[j].c;
    for(int i=0;i<m;i++)
        if(dist[mu[i].x] + mu[i].c < dist[mu[i].y])
            g<<"Ciclu negativ!", i=m+1, cn=true;
}
int main(){
    read();
    bellmanFord(1);
    if(cn)return 0;
    for(int i=2;i<=n;i++)
        g<<dist[i]<<" ";
    return 0;
    cout<<n<<"\n";
    for(int i=0;i<m;i++)
        cout<<mu[i].x<<" "<<mu[i].y<<" "<<mu[i].c<<"\n";
    return 0;
}