#include<fstream>
#include<vector>
#include<queue>
#define nmax 50005
#define inf (1<<30)
#define SI short int
using namespace std;
vector <pair<unsigned SI,SI> > G[nmax];
queue<int> Q;
int d[nmax],n,m,s,sw;
unsigned SI nr[nmax];
bool use[nmax];
void citire()
{
	ifstream f("dijkstra.in");
	int x,y,c;
	f>>n>>m;
	for(int i=0;i<m;i++)
	{
		f>>x>>y>>c;
		G[x].push_back(make_pair(y,c));
	}
	f.close();
}
void DFS(int nod)
{
	unsigned int i;
	int vec,cost;
	for(i=0;i<G[nod].size();i++)
		if(d[nod]!=inf)
		{
			vec=G[nod][i].first;
			cost=G[nod][i].second;
			if(d[vec]>d[nod]+cost)
			{
				d[vec]=d[nod]+cost;
				if(!use[vec])
				{
					if(nr[vec]>n)
						sw=1;
					else
					{
						Q.push(vec);
						use[vec]=1;
						nr[vec]++;
					}
				}
			}
		}
}
void print()
{
	ofstream g("dijkstra.out");
	if(!sw)
		for(int i=2;i<=n;i++)
			g<<d[i]<<' ';
	else
		g<<"Ciclu negativ!";
	g<<'\n';
	g.close();
}
void solve()
{
	int nod;
	Q.push(1);
	use[1]=1;
	while(!Q.empty() && !sw)
	{
		nod=Q.front();
		Q.pop();
		use[nod]=0;
		DFS(nod);
	}
	print();
}
int main()
{
	for(unsigned int i=2;i<nmax;i++)
		d[i]=inf;
	citire();
	solve();
	return 0;
}