#include <fstream>
#include <vector>
#include <queue>
#include <string.h>
#define TR(C, i)\
    for(typeof(C.begin()) i = C.begin(); i != C.end(); i++)


using namespace std;

ifstream in ("bellmanford.in");
ofstream out ("bellmanford.out");

const int oo = 0x3f3f3f3f;
const int nmax = 50010;
int N, M;
vector< pair<int, int> > G[nmax];
int D[nmax];

void citire()
{
	in >> N >> M;

	for(int i = 1; i <= M; ++i)
	{
		int x, y, d;
		in >> x >> y >> d;
		G[x].push_back(make_pair(y, d));
	}
}

struct cmp
{
    bool operator()(const int &a, const int &b)const
    {
        return D[a] > D[b];
    }
};

priority_queue <int, vector<int>, cmp> Q;

bool In[nmax];
int scos[nmax];

void solve()
{
    memset(D, 0x3f, sizeof(D));

    D[1] = 0;
    In[1] = true;
    Q.push(1);

    int nod;
    while(!Q.empty())
    {
        nod = Q.top();
        Q.pop();
        In[nod] = 0;
        ++scos[nod];

        if(scos[nod] > N)
        {
            out << "Ciclu negativ!";
            return;
        }

        TR(G[nod], it)
            if(D[it->first] > D[nod] + it->second)
            {
                D[it->first] = D[nod] + it->second;

                if(In[it->first])continue;

                Q.push(it->first);
                In[it->first] = 1;
            }
    }
    int i;
    for(i = 2; i <= N; i++)
        out << D[i] << ' ';
    out << '\n';
}

int main()
{
    citire();
    solve();
    return 0;
}