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

int n,m;
int aparitii[NMAX];
int dist[NMAX];
typedef pair <int,int> pereche;
vector < vector < pereche > > Graf;
queue <int> q;
bool negativ;

inline void read(){

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

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

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

inline void Bellman_Ford(){

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

    dist[1] = 0;
    q.push(1);
    int nod;
        while(!q.empty() && !negativ){

            nod = q.front();
            q.pop();
            for(vector <pereche>::iterator it = Graf[nod].begin();it!=Graf[nod].end();++it)
                if(dist[it->first] > dist[nod] + it->second){
                    dist[it->first] = dist[nod] + it->second;
                    q.push(it->first);
                    ++aparitii[it->first];
                    if(aparitii[it->first] > n)
                        negativ = 1;
                }
        }
}

inline void write(){

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

int main(){

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

return 0;
}