# include <cstdio>
# include <queue>
# include <utility>
# define pb push_back
# define mp make_pair
# define N 50010
# define INF 2000000000
# define cost (*it).second
# define vecin (*it).first

using namespace std;

int n,m,x,y,c,ciclu_negativ;
bool sel[N];
int C[N],fr[N];
queue <int> q;
vector < pair<int,int> > G[N];
vector < pair<int,int> > :: iterator it;

int main()
{
    freopen("bellmanford.in", "r", stdin);
    freopen("bellmanford.out", "w", stdout);

    scanf("%d %d\n", &n, &m);
    for(int i=1; i<=m; ++i)
    {
        scanf("%d %d %d", &x, &y, &c);
        G[x].pb(mp(y,c));
    }
    for(int i=1; i<=n; ++i)
        C[i]=INF;

    q.push(1);
    sel[1]=1;
    C[1]=0;
    while(!q.empty() && !ciclu_negativ)
    {
        int nod=q.front();
        q.pop();
        sel[nod]=0;
        for(it=G[nod].begin(); it!=G[nod].end(); ++it)
            if(C[nod]+cost<C[vecin])
            {
                C[vecin]=C[nod]+cost;
                if(!sel[vecin])
                {
                    q.push(vecin);
                    sel[vecin]=1;
                    fr[vecin]++;
                    if(fr[vecin]>n) ciclu_negativ=1;
                }
            }
    }

    if(ciclu_negativ)
    {
        printf("Ciclu negativ!\n");
        return 0;
    }

    for(int i=2; i<=n; ++i)
        printf("%d ", C[i]);

    return  0;
}