#include <cstdio>
#include <vector>
#include <cstring>
#include <queue>
#define PB push_back
#define MP make_pair
#define F first
#define S second
#define INF 1<<30
#define MX 50005
#define nod  (*it).F
#define cost (*it).S
using namespace std;
vector < pair <int,int> > G[MX];
queue <int> q;
vector < pair <int,int> > :: iterator it;
bool u[MX],negativ=false;
int fr[MX];
int dist[MX];
int x,y,m,n,cst;
int main()
{
    freopen("bellmanford.in","r",stdin);
    freopen("bellmanford.out","w",stdout);
    scanf("%d %d",&n,&m);
    for(int w=1; w<=n; w++)
    {
        dist[w]=INF;
    }
    while(m--)
    {
        scanf("%d %d %d",&x,&y,&cst);
        G[x].PB(MP(y,cst));
    }
    int w;
    dist[1]=0;
    q.push(1);
    while(!q.empty() && !negativ)
    {
        w=q.front();
        u[w]=false;
        q.pop();
        for(it=G[w].begin(); it!=G[w].end(); it++)
        {
            if(dist[nod]>dist[w]+cost)
            {
                dist[nod]=dist[w]+cost;
                if(!u[nod])
                {

                    fr[nod]++;
                    if(fr[nod]>n)
                    {
                        printf("Ciclu negativ!");
                        return 0;
                    }
                    q.push(nod);
                    u[nod]=true;
                }
            }
        }



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

    return 0;
}