#include <cstdio>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>

#define nmax 50001
#define inf 0x3f3f3f3f
#define nod first
#define cost second
using namespace std;

vector <pair <int,int> > g[nmax];
vector <pair <int,int> >::iterator vecin;
queue <int> q;

int n,i,m,x,y,c,cost[nmax],itnod[nmax],nod;
bool used[nmax];

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

    scanf("%d %d",&n,&m);

    for (i=1;i<=m;i++)
    {
        scanf("%d %d %d",&x,&y,&c);
        g[x].push_back(make_pair(y,c));
    }

    memset(used,false,sizeof(used)); //niciun nod nu e folosit inca in coada
    memset(itnod,0,sizeof(itnod)); //nu am trecut prin niciun nod
    memset(cost,inf,sizeof(cost)); //toate costurile initial sunt infinit
    cost[1]=0; //costul de sursa la sursa este 0
    q.push(1); //adaugam nodul sursa in coada
    used[1]=true; //nodul a fost folosit
    while (!q.empty()) //cat timp mai sunt noduri in coasa
    {
        nod=q.front();
        q.pop();
        used[nod]=false;//nodul a fost scos din coada
        for (vecin=g[nod].begin();vecin!=g[nod].end();vecin++) //iteram prin fiecare din vecinii nodului curent
        {
            if (cost[(*vecin).nod]>cost[nod]+(*vecin).cost) //daca costul curent este mai mare, il imbunatatim
            {
                cost[(*vecin).nod]=cost[nod]+(*vecin).cost; // actualizam costul

                if (!used[(*vecin).nod]) //verificam daca nodul vecin este in coada
                {
                    q.push((*vecin).nod); // introducem nodul in coada
                    used[(*vecin).nod]=true; //il marcam in vector ca prezent in coada
                    if (++itnod[(*vecin).nod]>n) // daca numarul de iteratii prin acel nod este mai mare decat n, avem un ciclu negativ
                    {
                        printf("Ciclu negativ!\n");
                        return 0;
                    }
                }
            }
        }
    }
    for (i=2;i<=n;i++)
        printf("%d ",cost[i]);
    return 0;
}