#include <bits/stdc++.h>
#define oo 20000
using namespace std;
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");
int n,m,start = 1;
int a[20000][20000];
int d[32000],pre[32000];
void Citire()
{
    int x,y,c;
    f>>n>>m;
    for(int i=1;i<=n;++i)
        for(int j=1;j<=n;++j)
            a[i][j] = oo;
    for(int i=1;i<=m;++i)
    {
        f>>x>>y>>c;
        a[x][y] = c;
    }
    for(int i=1;i<=n;++i)
    {
        d[i] = a[start][i];
        pre[i] = start;
    }
    pre[start] = 0;
    d[start] = 0;
}

bool Bellman_Ford()
{
    for(int i=1;i<=n;++i)
        for(int j=1;j<=n;++j)
            for(int k=1;k<=n;++k)
                if(a[j][k] != oo && d[k] > d[j] + a[j][k])
                {
                    pre[k] = j;
                    d[k] = d[j] + a[j][k];
                }
    for(int i=1;i<=n;++i)
        for(int j=1;j<=n;++j)
            if(a[i][j] != oo && d[j] > d[i] + a[i][j])
            {
                g<<"Ciclu negativ!";
                return false;
            }
    return true;
}

int main()
{
    Citire();
    if(Bellman_Ford())
    {
        for(int i=2;i<=n;++i)
            g<<d[i]<<" ";
    }
    return 0;
}