#include <fstream>
#include <vector>
#include <queue>
#define pr pair<int,int>
#define nmax 50001
#define INF 0x3f3f3f3f
using namespace std;
ifstream is ("bellmanford.in");
ofstream os ("bellmanford.out");

vector <pr> V[nmax];
vector <int> cnt(nmax, 0), D(nmax, INF);
vector <bool> in_queue(nmax, false);
queue <int> Q;
int N, M;
bool inf;

void Read();
void BellmanFord();

int main()
{
    Read();
    Q.push(1);
    D[1] = 0;
    in_queue[1] = true;
    cnt[1]++;
    BellmanFord();
    if(inf) os << "Ciclu negativ!";
    else
    for(int i = 2; i <= N; ++i)
        os << D[i] << " ";
    is.close();
    os.close();
    return 0;
}
void Read()
{
    int x, y, c;
    is >> N >> M;
    for(int i = 1; i <= M; ++i)
    {
        is >> x >> y >> c;
        V[x].push_back({y, c});
    }
}
void BellmanFord()
{
    vector<pr>::iterator it;
    int node;
    while(!Q.empty() && !inf)
    {
        node = Q.front();
        Q.pop();
        in_queue[node] = false;

        for(it = V[node].begin(); it != V[node].end(); ++it)
        {
            if(D[it->first] > D[node] + it->second)
            {
                D[it->first] = D[node] + it->second;
                if(!in_queue[it->first])
                {
                    if(cnt[it->first] > N)
                        inf = true;
                    else
                    {
                        cnt[it->first]++;
                        Q.push(it->first);
                        in_queue[it->first] = true;
                    }
                }

            }
        }
    }
}