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

#define N_MAX 50010
#define vecin first
#define cost second
#define pb push_back
#define pf pop_front
#define mp make_pair
#define INF 600000
using namespace std;

vector < pair<int,int> > G[N_MAX];
deque <int> Q;

int D[N_MAX],use[N_MAX],N;
bool pus[N_MAX],Ciclu_Neg=false;

inline void Write_Data()
{
    int i;
    for (i=2;i<=N;i++)
        if (D[i]!=INF) printf("%d ",D[i]);
            else printf("0 ");
    printf("\n");
}

inline void Bellman()
{
    int nod;
    vector < pair<int,int> > :: iterator it;
    pair <int,int> muchie;
    while (!Q.empty())
    {
        nod=Q.front();
        Q.pf();
        pus[nod]=false;
        for (it=G[nod].begin();it!=G[nod].end();++it)
        {
            muchie=*it;
            if (D[muchie.vecin] > D[nod]+muchie.cost)
                {
                    D[muchie.vecin]=D[nod]+muchie.cost;
                    if (!pus[muchie.vecin])
                        {
                            Q.pb(muchie.vecin);
                            pus[muchie.vecin]=true;
                            use[muchie.vecin]++;
                            if (use[muchie.vecin]>N)
                                {
                                    Ciclu_Neg=true;
                                    printf("Ciclu negativ!\n");
                                    return;
                                }
                        }
                }
        }
    }
}

inline void Load_Data()
{
    int M,x,y,c,i;
    scanf("%d%d",&N,&M);
    for (i=1;i<=M;i++)
        scanf("%d%d%d",&x,&y,&c), G[x].pb(mp(y,c));
    for (i=1;i<=N;i++)
        D[i]=INF, use[i]=0, pus[i]=false;
    Q.pb(1);
    D[1]=0;
    pus[1]=true;
}

int main()
{
    freopen("bellmanford.in","r",stdin);
    freopen("bellmanford.out","w",stdout);
    Load_Data();
    Bellman();
    if (!Ciclu_Neg) Write_Data();
    fclose(stdin);
    fclose(stdout);
    return 0;
}