# include <cstdio>
# include <vector>
# include <cstring>

# define pb push_back
# define mp make_pair
# define vecin (*it).first
# define cost (*it).second
# define INF (1<<30)
# define nod Q[i]

# define N 50010

using namespace std;

vector < pair < int , int > > G[N];
vector < pair < int , int > > :: iterator it;

bool sel[N];
int Q[N],C[N],fr[N],T[N];
int ciclu_negativ;
int n,m;

void load()
{
    int x,y,c;
    freopen("bellmanford.in", "r", stdin);
    scanf("%d %d\n", &n, &m);
    for(int i=1; i<=n; ++i)
    {
        scanf("%d %d %d\n", &x, &y, &c);
        G[x].pb(mp(y,c));
    }
    for(int i=1; i<N; ++i) C[i]=INF;
    fclose(stdin);
    return;
}

void bellman()
{
    Q[++Q[0]]=1;
    C[1]=0;
    for(int i=1; i<=Q[0]; ++i)
    {
        sel[nod]=0;
        for(it=G[nod].begin(); it!=G[nod].end(); ++it)
            if(cost+C[nod]<C[vecin])
            {
                C[vecin]=C[nod]+cost;
                T[vecin]=nod;
                if(!sel[vecin])
                {
                    if(++fr[vecin]>n)
                    {
                        ciclu_negativ=1;
                        return;
                    }
                    Q[++Q[0]]=vecin;
                    sel[vecin]=1;
                }
            }
    }
}

void write()
{
    freopen("bellmanford.out", "w", stdout);
    if(ciclu_negativ)
    {
        printf("Ciclu negativ!\n");
        return;
    }
    for(int i=2; i<=n; ++i) printf("%d ", C[i]);
    fclose(stdout);
    return;
}

int main()
{
    load();
    bellman();
    write();
}