#include <fstream>
#include <vector>
#include <queue>

#define NLen 65535
#define inf 0x7fffffff

using namespace std;

ifstream cin;
ofstream cout;

struct graf
{
    int adj, cost;
};

vector < graf > g[NLen];

int dist[NLen];

inline graf make(int adj, int cost)
{
    graf ret;
    ret.adj = adj;
    ret.cost = cost;
    return ret;
}

inline int bf(int nod, int N)
{
    int use[NLen];
    int cnt[NLen];
    queue < int > q;

    q.push(nod);
    use[nod] = 1;
    dist[nod] = 0;

    while( ! q.empty())
    {
        nod = q.front();
        q.pop();
        use[nod] = 0;

        for(int i = 0; i < g[nod].size(); ++ i)
            if(dist[ g[nod][i].adj ] > dist[nod] + g[nod][i].cost)
            {
                if( ! use[ g[nod][i].adj ])
                {
                    use[ g[nod][i].adj ] = 1;
                    q.push(g[nod][i].adj);
                }

                if( ++ cnt[ g[nod][i].adj ] >= N) return - 1;

                dist[ g[nod][i].adj ] = dist[nod] + g[nod][i].cost;
            }
    }

    return 1;
}

int main()
{
    cin.open("bellmanford.in");
    cout.open("bellmanford.out");

    int N, M;
    cin >> N >> M;

    while(M -- )
    {
        int x, y, c;
        cin >> x >> y >> c;

        g[x].push_back(make(y, c));
    }

    for(int i = 1; i <= N; ++ i) dist[i] = inf;

    if(bf(1, N) == - 1) cout << "Ciclu negativ!";
    else
    for(int i = 2; i <= N; ++ i) cout << dist[i] << ' ';

    cout << '\n';

    cin.close();
    cout.close();

    return 0;
}