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

#define DIM 50010
#define INF 1000000000

using namespace std;
ifstream fin("bellmanford.in");
ofstream fout("bellmanford.out");

vector<vector<pair<int, int> > > G;
bitset<DIM> v;
vector<int> d;
int N[DIM];

int n, m;

void ReadGraph()
{
int x,y,w;
fin >> n >> m;
G.resize(n+1);
d.resize(n+1);

    for (int i = 1;i <= m; i++)
    {
        fin >> x >> y >> w;
        G[x].push_back({y,w});
    }
}

void Bellmanford(int x,vector<int> & d)
{   queue<int> Q;
    d=vector<int>(n+1,INF);

    v[1] = 1;
    d[1] = 0;


 for ( Q.push(1); !Q.empty(); Q.pop())
    {
        x = Q.front();
        v[x] = 0;

        for (auto & p : G[x])
        {
            int y = p.first;
            int w = p.second;
            if (d[y] > d[x] + w)
            {
                d[y] = d[x] + w;
                if (!v[y])
                {
                    N[y]++;
                    if (N[y] == n)
                    {
                        fout<<"Ciclu negativ!";
                        n=0;
                        return ;
                    }
                    Q.push(y);
                    v[y] = 1;
                }
            }
        }
    }

}

int main()
{

ReadGraph();
Bellmanford(1,d);
for (int i = 2; i <= n; i++)
        fout << d[i] << " ";

    return 0;
}