# include <cstdio>
# include <vector>
# include <queue>
using namespace std;

FILE *f = freopen("bellmanford.in", "r", stdin);
FILE *g = freopen("bellmanford.out", "w", stdout);

const int N_MAX = 500001;
const int INF = 0x3fffffff;

struct vecin{
    int capat;
    int cost;

    vecin (int &a, int &b)
    {
        this -> capat = a;
        this -> cost = b;
    }
};

int n, m;
vector <vecin> G[N_MAX];
queue <int> q;
int vizitat[N_MAX];
bool inqueue[N_MAX];
int dstart[N_MAX];

void bellman()
{
    q.push(1);

    for (int i=2; i<=n; i++)
    {
        vizitat[i] = 0;
        dstart[i] = INF;
    }

    while (!q.empty() && vizitat[q.front()] < n)
    {
        int nod = q.front();
        q.pop();
        inqueue[nod] = false;

        for (vecin i : G[nod])
        {
            if (dstart[i.capat] > dstart[nod] + i.cost)
            {
                dstart[i.capat] = dstart[nod] + i.cost;
                if (!inqueue[i.capat])
                {
                    q.push(i.capat);
                    inqueue[i.capat] = true;
                }
            }

            vizitat[i.capat] ++;
        }
    }

    if (q.empty())
    {
        for (int i=2; i<=n ;i++)
            printf("%d ", dstart[i]);
    }
    else
    {
        printf("Ciclu negativ!");
    }
}

int main()
{
    scanf("%d %d", &n, &m);

    for (int i=1; i<=m; i++)
    {
        int x, y, c;
        scanf("%d %d %d", &x, &y, &c);

        G[x].push_back(vecin(y, c));
    }

    bellman();
    return 0;
}