#include<fstream>
#include<vector>
#include<queue>
#include<bitset>
using namespace std;
const int MAXN=50010;
const int INF=1<<30;
struct edge{int dest,cost;};
int n,m;
int dist[MAXN],in_queue[MAXN];
queue<int> q;
vector<edge> adj[MAXN];

void read()
{
    ifstream fin("bellmanford.in");
    fin>>n>>m;

    edge aux;
    int x,y,c;
    for (int k=1; k<=m; ++k)
    {
        fin>>x>>y>>c;
        aux.dest=y;
        aux.cost=c;
        adj[x].push_back(aux);
    }
    fin.close();
}
bool bellman_ford()
{
    int i;
    for (i=2; i<=n; dist[i]=INF, ++i);
    for (i=1; i<=n-1; ++i)
    {
        q.push(1);
        while (!q.empty())
        {
            int aux=q.front();
            ++in_queue[aux];
            if (in_queue[aux]==n)
                return false;
            for (vector<edge>::iterator k=adj[aux].begin(); k!=adj[aux].end(); ++k)
            {
                if (dist[k->dest]>dist[aux]+k->cost)
                {
                    dist[k->dest]=dist[aux]+k->cost;
                    q.push(k->dest);
                }
            }
            q.pop();
        }
    }
    return true;
}
void write()
{
    ofstream fout("bellmanford.out");
    bool rez=bellman_ford();
    if (!rez)
        fout<<"Ciclu negativ!";
    else
        for (int i=2; i<=n; fout<<dist[i]<<' ', ++i);
    fout<<'\n';
    fout.close();
}
int main()
{
    read();
    write();
    return 0;
}