#include <cstdio>
#include <vector>
#include <queue>
#include <utility>
#define INF 0x3f3f3f3f
#define NMAX 50000
using namespace std;

int n,m,negative;
int dist[NMAX];
int apearances[NMAX];
typedef pair < int, int > pereche;
queue < int > q;
vector < pereche > Graph[NMAX];

void read(){

    int x,y,c;
    freopen("bellmanford.in","r",stdin);
    freopen("bellmanford.out","w",stdout);
    scanf("%d%d",&n,&m);

    for(register int i=1;i<=m;++i){

        scanf("%d%d%d",&x,&y,&c);
        Graph[x].push_back(pereche(y,c));
        }
}

void Bellman_Ford(){

    q.push(1);
    for(register int i=1;i<=n;++i)
        dist[i] = INF;

    dist[1] = 0;

        while(!q.empty() && !negative){

                int node = q.front();
                q.pop();

                    for(vector < pereche > ::iterator it = Graph[node].begin(); it != Graph[node].end(); ++it)
                    if(dist[it->first] > dist[node] + it->second){
                            dist[it->first] = dist[node] + it->second;
                            q.push(it->first);
                            apearances[it->first]++;
                            if(apearances[it->first] > n)
                                    negative = 1;
                    }
        }
}

void write(){

    if(negative)
            printf("Ciclu negativ!");
    else
            for(register int i=2;i<=n;++i)
            printf("%d ", dist[i]);

}

int main(){

    read();
    Bellman_Ford();
    write();

return 0;
}