#include <fstream>
#include <vector>
#include <queue>
#define N 50005
#define INF 10000000
using namespace std;

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

struct bell{
    int nod, cost;
};

int n, m;
int cost[N], viz[N];
vector<bell> graf[N];
queue<int> coada;
bool sem = 1;

void bellmanford(){
    while(!coada.empty()){
        int nod = coada.front();
        coada.pop();
        viz[nod]++;

        if(viz[nod] >= n){
            sem = 0;
            return;
        }

        for(unsigned i = 0; i < graf[nod].size(); ++i){
            if(cost[graf[nod][i].nod] > cost[nod] + graf[nod][i].cost){
                cost[graf[nod][i].nod] = cost[nod] + graf[nod][i].cost;
                coada.push(graf[nod][i].nod);
            }

        }
    }
}

int main()
{
    in>>n>>m;
    for(int i = 1; i <= m; ++i){
        int x; bell nod;
        in>>x>>nod.nod>>nod.cost;

        graf[x].push_back(nod);
    }

    for(int i = 2; i <= n; ++i)
        cost[i] = INF;

    coada.push(1);
    bellmanford();

    if(sem == 0) out<<"Ciclu negativ!";
    else for(int i = 2;i <= n; ++i)
        out<<cost[i]<<" ";



    in.close();
    out.close();
    return 0;
}