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

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

struct ura
{
    int cost;
    int vecin;
};

vector<ura> v[50001];
long long dmin[50001];
deque<int> q;
bool in_q[50001];
int cont[50001];

int main()
{
    int n, m, cnt;
    cin>>n>>m;
    dmin[1] = 0;
    q.push_back(1);
    in_q[1] = true;
    cnt = 1;
    cont[1]++;
    for(int i=2; i<=n; i++)
    {
        dmin[i] = 1e18;
    }
    for(int i=1; i<=m; i++)
    {
        int x, y, c;
        cin>>x>>y>>c;
        v[x].push_back({c, y});
    }
    bool pp = 1;
    while(q.size())
    {
        int x, y, c;
        pp=0;
        x = q[0];
        q.pop_front();
        cnt++;
        for(int j=0; j<v[x].size(); j++)
        {
            c = v[x][j].cost;
            y = v[x][j].vecin;
            if(dmin[x] + c < dmin[y])
            {
                dmin[y] = dmin[x] + c;
                pp = 1;
                if(in_q[y] == false)
                {
                    q.push_back(y);
                    in_q[y] = true;
                    cont[y]++;
                    if(cont[y] > n)
                    {
                        cout<<"Ciclu negativ!";
                        return 0;
                    }
                }
            }
        }
        in_q[x] = false;
    }
    for(int i=2; i<=n; i++)
        cout<<dmin[i]<<" ";
    return 0;
}