#include <fstream>
#include <vector>
using namespace std;
ifstream cin("bellmanford.in");
ofstream cout("bellmanford.out");
const int INF=1e9;
int n,m1;
int dp[50002];
struct elem{
    int x,y,c;
};
vector<elem> m;
int main()
{
    cin>>n>>m1;
    m.resize(m1+1);
    for(int i=1;i<=n;i++)
        dp[i]=INF;
    for(int i=1;i<=m1;i++)
        cin>>m[i].x>>m[i].y>>m[i].c;
    dp[1]=0;
    for(int i=1;i<n;i++)
    {
        for(int j=1;j<=m1;j++)
        {
            if(dp[m[j].y]>dp[m[j].x]+m[j].c)
                dp[m[j].y]=dp[m[j].x]+m[j].c;
        }
    }
    for(int j=1;j<=m1;j++)
        if(dp[m[j].y]>dp[m[j].x]+m[j].c)
        {
            cout<<"Ciclu negativ!";
            return 0;
        }
    for(int i=2;i<=n;i++)
        cout<<dp[i]<<" ";
    return 0;
}