#include <stdio.h>
#include <queue>
#include <cstring>
#define N_MAX 50003
#define INFINIT 999999

using namespace std;

int n, m;
int dmin[N_MAX];
int counts[N_MAX];
queue <int> coada;
vector< pair<int, int> > lists[N_MAX];

void citire();
bool Bellman_Ford(int);
void afisare();

int main()
{
    citire();
    bool isNegativ = Bellman_Ford(1);

    if (isNegativ){
        printf("Ciclu negativ!\n");
        return 0;
    }
    afisare();

    return 0;
}

void citire(){
    freopen("bellmanford.in", "r", stdin);
    freopen("bellmanford.out", "w", stdout);

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

    int x, y, z;

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

bool Bellman_Ford(int start){
    int nod;
    int i;
    int v_size;

    memset(dmin, INFINIT, sizeof(dmin));
    dmin[start] = 0;
    coada.push(start);

    while (!coada.empty()){
        nod = coada.front();
        coada.pop();
        v_size = lists[nod].size();
        for (i = 0; i < v_size; ++i){
            if (dmin[lists[nod][i].first] > dmin[nod] + lists[nod][i].second){
                dmin[lists[nod][i].first] = dmin[nod] + lists[nod][i].second;
                coada.push(lists[nod][i].first);
                counts[lists[nod][i].first]++;

                if (counts[lists[nod][i].first] > n)
                    return true;
            }
        }
    }
    return false;
}

void afisare(){
    for (int i = 2; i <= n; ++i){
        printf("%d ", dmin[i] < INFINIT ? dmin[i] : 0);
    }
    printf("\n");
}