#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>

using namespace std;

class Disjoint_set
{
	int noduri;
	vector<int>tata; // vector in care sunt stocati reprezentantii componentelor/arborilor(reprezentantul arborelui este radacina sa)
	vector<int>h; // vector in care este stocata inaltimea arborilor

public:
	Disjoint_set(int n);
	void initializare(); // initializarea vectorului de tati/reprezentanti si a vectorului de inaltimi
	int reprezentant(int varf); // determinarea radacinii arborelui care contine varf
	void reuneste(int varf1, int varf2); // reuniunea componentelor care contin varf1 si varf2
	void solve_paduri_de_multimi_disjuncte(ifstream& f, ofstream& o);

};

Disjoint_set::Disjoint_set(int n)
{
	noduri = n;
}

void Disjoint_set::initializare()
{
	tata.resize(noduri + 1, 0);
	h.resize(noduri + 1, 0);
}

int Disjoint_set::reprezentant(int varf)
{
	while (tata[varf] != 0)
		varf = tata[varf];

	return varf;
}

void Disjoint_set::reuneste(int varf1, int varf2)
{
	int rv1, rv2;

	rv1 = reprezentant(varf1);
	rv2 = reprezentant(varf2);

	if (h[rv1] > h[rv2]) // reuniunea se face in functie de inaltimea arborilor(arborele cu inaltime mai mica devine subarbore al radacinii celuilalt arbore)
		tata[rv2] = rv1;

	else
	{
		tata[rv1] = rv2;
		if (h[rv1] == h[rv2])
			h[rv2] ++;
	}
}

void Disjoint_set::solve_paduri_de_multimi_disjuncte(ifstream& f, ofstream& o)
{
	int nr_operatii;

	f >> nr_operatii;

	initializare();

	for (int i = 0; i < nr_operatii; i++)
	{
		int cod, x, y;

		f >> cod >> x >> y;

		if (cod == 1)
			reuneste(x, y);

		else
		{
			if (reprezentant(x) == reprezentant(y))
				o << "DA" << "\n";
			else
				o << "NU" << "\n";
		}
	}

}

class Graf
{
	int noduri, muchii;

	void bfs_si_distante(int varf, vector<vector<int>>& vecini, vector<bool>& vizitat, vector<int>& distanta_minima); // parcurgere in latime + determinarea distantelor celorlalte varfuri fata de un varf de start
	void dfs(int varf, vector<vector<int>>& vecini, vector<bool>& vizitat); // parcurgere in adancime
	void dfs_si_timp_de_finalizare(int varf, vector<vector<int>>& vecini, vector<bool>& vizitat, stack<int>& stiva_rezultat); // parcurgere in adancime + determinarea timpilor de finalizare: momentul cand se termina de vizitat vecinii unui varf x (si toti vecinii/descendentii acestora), iar varful x este eliminat de pe stiva
	void dfs_graf_transpus(int varf, vector<vector<int>>& vecini_transpus, vector<bool>& vizitat_transpus, vector<vector<int>>& componente_tare_conexe, int nr_componenete_tare_conexe); // parcurgere in adancime a grafului transpus + memorarea componentelor tare conexe
	void Dijkstra(int start, vector<vector<pair<int, int>>>& vecini, vector<int>& d, priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>& q);
	bool Bellman_Ford(int start, vector<vector<pair<int, int>>>& vecini, vector<int>& d);

public:
	Graf(int n, int m);
	void solve_bfs_distanta_minima(ifstream& f, ofstream& o);
	void solve_componente_conexe(ifstream& f, ofstream& o);
	void solve_sortare_topologica(ifstream& f, ofstream& o);
	void solve_componente_tare_conexe(ifstream& f, ofstream& o);
	void solve_arbore_partial_de_cost_minim_Kruskal(ifstream& f, ofstream& o);
	void solve_Dijkstra(ifstream& f, ofstream& o);
	void solve_Bellman_Ford(ifstream& f, ofstream& o);

};

Graf::Graf(int n, int m)
{
	noduri = n;
	muchii = m;
}

void Graf::bfs_si_distante(int varf, vector<vector<int>>& vecini, vector<bool>& vizitat, vector<int>& distanta_minima)
{
	queue<int>coada; // coada in care salvez varfurile care sunt vizitate si care urmeaza sa fie explorate(adica cercetez vecinii lor)

	vizitat[varf] = 1; // marchez varful de start ca fiind vizitat

	coada.push(varf); // adaug varful de start in coada pentru a-l explora

	while (coada.size()) // cat timp mai am noduri de explorat
	{
		varf = coada.front(); // extrag un varf din coada pentru a-l explora

		// cout << varf << " "; 

		coada.pop();

		for (int j = 0; j < vecini[varf].size(); j++) //marchez toate varfurile adiacente cu el si nevizitate anterior, iar apoi le introduc in coada
			if (!vizitat[vecini[varf][j]])
			{
				vizitat[vecini[varf][j]] = 1;

				coada.push(vecini[varf][j]);

				distanta_minima[vecini[varf][j]] = distanta_minima[varf] + 1; // distanta unui varf nou adaugat este distanta varfului care l-a adaugat + 1
			}
	}
}

void Graf::solve_bfs_distanta_minima(ifstream& f, ofstream& o)
{
	int varf_start; // varful din care trebuie sa incepem parcurgerea

	f >> varf_start;

	vector<vector<int>>vecini; // liste de adiacenta
	vector<bool>vizitat; // vector in care se marcheaza varfurile vizitate
	vector<int>distanta_minima; // vector in care stochez distantele fata de varful de start

	vecini.resize(noduri + 1);
	vizitat.resize(noduri + 1, 0);
	distanta_minima.resize(noduri + 1, 0);

	for (int i = 0; i < muchii; i++)
	{
		int x, y; // extremitatile unui arc

		f >> x >> y;

		vecini[x].push_back(y);
	}

	for (int i = 1; i <= noduri; i++)
		sort(vecini[i].begin(), vecini[i].end());

	bfs_si_distante(varf_start, vecini, vizitat, distanta_minima);

	for (int i = 1; i <= noduri; i++)
		if (i != varf_start && distanta_minima[i] == 0)
			o << "-1 ";
		else
			o << distanta_minima[i] << " ";

}

void Graf::dfs(int varf, vector<vector<int>>& vecini, vector<bool>& vizitat)
{
	// cout << varf << " ";

	vizitat[varf] = 1; // marchez varful de start ca fiind vizitat

	for (int j = 0; j < vecini[varf].size(); j++) // aleg mereu primul vecin nevizitat anterior al varfului curent
		if (!vizitat[vecini[varf][j]])
			dfs(vecini[varf][j], vecini, vizitat);
}

void Graf::solve_componente_conexe(ifstream& f, ofstream& o)
{
	vector<vector<int>>vecini; // liste de adiacenta
	vector<bool>vizitat; // vector in care se marcheaza varfurile vizitate

	vecini.resize(noduri + 1);
	vizitat.resize(noduri + 1, 0);

	for (int i = 0; i < muchii; i++)
	{
		int x, y; // extremitatile unei muchii

		f >> x >> y;

		vecini[x].push_back(y);
		vecini[y].push_back(x);

	}

	for (int i = 1; i <= noduri; i++)
		sort(vecini[i].begin(), vecini[i].end());

	int componenete_conexe = 0;

	for (int i = 1; i <= noduri; i++) // pentru fiecare varf ramas nevizitat incrementez variabila componente_conexe si apelez functia de parcurgere in adancime
		if (!vizitat[i])
		{
			componenete_conexe += 1;

			dfs(i, vecini, vizitat);
		}

	o << componenete_conexe;
}

void Graf::dfs_si_timp_de_finalizare(int varf, vector<vector<int>>& vecini, vector<bool>& vizitat, stack<int>& stiva_rezultat)
{
	// cout << varf << " ";

	vizitat[varf] = 1; // marchez varful de start ca fiind vizitat

	for (int j = 0; j < vecini[varf].size(); j++) // aleg mereu primul vecin nevizitat anterior al varfului curent
		if (!vizitat[vecini[varf][j]])
			dfs_si_timp_de_finalizare(vecini[varf][j], vecini, vizitat, stiva_rezultat);

	stiva_rezultat.push(varf); // varfurile sunt adaugate in stiva in ordinea descrecatoare a timpilor de finalizare 
}

void Graf::solve_sortare_topologica(ifstream& f, ofstream& o)
{
	vector<vector<int>>vecini; // liste de adiacenta
	vector<bool>vizitat; // vector in care se marcheaza varfurile vizitate
	stack<int>stiva_rezultat; // stiva in care sunt stocate varfurile in ordinea descrecatoare a timpilor de finalizare

	vecini.resize(noduri + 1);
	vizitat.resize(noduri + 1, 0);

	for (int i = 0; i < muchii; i++)
	{
		int x, y; // extremitatile unui arc

		f >> x >> y;

		vecini[x].push_back(y);
	}

	for (int i = 1; i <= noduri; i++)
		sort(vecini[i].begin(), vecini[i].end());

	for (int i = 1; i <= noduri; i++)
		if (!vizitat[i])
			dfs_si_timp_de_finalizare(i, vecini, vizitat, stiva_rezultat);

	while (stiva_rezultat.size())
	{
		o << stiva_rezultat.top() << " ";
		stiva_rezultat.pop();
	}
}

void Graf::dfs_graf_transpus(int varf, vector<vector<int>>& vecini_transpus, vector<bool>& vizitat_transpus, vector<vector<int>>& componente_tare_conexe, int nr_componenete_tare_conexe)
{
	// cout << varf << " ";

	componente_tare_conexe[nr_componenete_tare_conexe].push_back(varf);

	vizitat_transpus[varf] = 1; // marchez varful de start ca fiind vizitat

	for (int j = 0; j < vecini_transpus[varf].size(); j++) // aleg mereu primul vecin nevizitat anterior al varfului curent
		if (!vizitat_transpus[vecini_transpus[varf][j]])
			dfs_graf_transpus(vecini_transpus[varf][j], vecini_transpus, vizitat_transpus, componente_tare_conexe, nr_componenete_tare_conexe);

}

void Graf::solve_componente_tare_conexe(ifstream& f, ofstream& o)
{
	vector<vector<int>>vecini; // liste de adiacenta
	vector<bool>vizitat; // vector in care se marcheaza varfurile vizitate
	stack<int>stiva_rezultat; // stiva in care sunt stocate varfurile in ordinea descrecatoare a timpilor de finalizare
	vector<vector<int>>vecini_transpus; // liste de adiacenta pentru graful transpus
	vector<bool>vizitat_transpus; // vector in care se marcheaza varfurile vizitate din graful transpus
	int nr_componenete_tare_conexe = 0;
	vector<vector<int>>componente_tare_conexe; // stocarea componentelor tare conexe


	vecini.resize(noduri + 1);
	vizitat.resize(noduri + 1, 0);
	vecini_transpus.resize(noduri + 1);
	vizitat_transpus.resize(noduri + 1);
	componente_tare_conexe.resize(noduri + 1);

	for (int i = 0; i < muchii; i++)
	{
		int x, y; // extremitatile unui arc

		f >> x >> y;

		vecini[x].push_back(y);

		vecini_transpus[y].push_back(x);
	}

	for (int i = 1; i <= noduri; i++)
	{
		sort(vecini[i].begin(), vecini[i].end());
		sort(vecini_transpus[i].begin(), vecini_transpus[i].end());
	}

	for (int i = 1; i <= noduri; i++) // este parcurs graful si se determina timpii de finalizare 
		if (!vizitat[i])
			dfs_si_timp_de_finalizare(i, vecini, vizitat, stiva_rezultat);

	while (stiva_rezultat.size()) // graful transpus este parcurs in functie de timpii de finalirizare determinati mai sus
	{
		if (!vizitat_transpus[stiva_rezultat.top()])
		{
			nr_componenete_tare_conexe++;
			dfs_graf_transpus(stiva_rezultat.top(), vecini_transpus, vizitat_transpus, componente_tare_conexe, nr_componenete_tare_conexe);
		}

		stiva_rezultat.pop();
	}

	o << nr_componenete_tare_conexe << "\n";

	for (int i = 1; i <= noduri; i++)
	{
		if (componente_tare_conexe[i].size())
		{
			for (int j = 0; j < componente_tare_conexe[i].size(); j++)
				o << componente_tare_conexe[i][j] << " ";
			o << "\n";
		}
	}
}

void Graf::solve_arbore_partial_de_cost_minim_Kruskal(ifstream& f, ofstream& o)
{
	struct muchie // structura folosita pentru a stoca inf despre o muchie: extremitatile si costul ei
	{
		int x, y, cost;

		bool operator <(const muchie& b)
		{
			return cost < b.cost;
		}
	};

	vector<muchie>v_muchii; // vector in care sunt stocate muchiile si costul lor
	v_muchii.resize(muchii);

	for (int i = 0; i < muchii; i++)
		f >> v_muchii[i].x >> v_muchii[i].y >> v_muchii[i].cost;

	sort(v_muchii.begin(), v_muchii.end()); // sortez crescator muchiile dupa cost

	Disjoint_set d(noduri);

	d.initializare();

	int cost_arbore, nr_muchii;

	cost_arbore = nr_muchii = 0;

	vector<pair<int, int>>de_afisat; // vector in care sunt stocate extremitatile muchiilor ce alcatuiesc arborele partial de cost minim

	for (int i = 0; i < muchii; i++)
	{
		int repr_x = d.reprezentant(v_muchii[i].x);
		int repr_y = d.reprezentant(v_muchii[i].y);

		if (repr_x != repr_y)
		{
			cost_arbore += v_muchii[i].cost;

			de_afisat.push_back(make_pair(v_muchii[i].x, v_muchii[i].y));

			d.reuneste(v_muchii[i].x, v_muchii[i].y);

			nr_muchii += 1;

			if (nr_muchii == noduri - 1)
				break;

		}
	}

	o << cost_arbore << "\n";
	o << nr_muchii << "\n";

	for (auto i : de_afisat)
		o << i.first << " " << i.second << "\n";
}

void Graf::Dijkstra(int start, vector<vector<pair<int, int>>>& vecini, vector<int>& d, priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>& q)
{
	d[start] = 0;

	for (int i = 1; i <= noduri; i++)
		q.push(make_pair(d[i], i));

	while (!q.empty())
	{
		int u = q.top().second; // extragem varful cu eticheta minima din q
		q.pop();

		for (auto i = vecini[u].begin(); i != vecini[u].end(); i++) // pentru fiecare muchie uv din E => relaxare
		{
			int v = i->first;
			int lungime = i->second;

			if (d[v] > (d[u] + lungime))
			{
				d[v] = d[u] + lungime; // actualizam lungimea pana la v
				q.push(make_pair(d[v], v));
			}
		}
	}
}

void Graf::solve_Dijkstra(ifstream& f, ofstream& o)
{
	vector<vector<pair<int, int>>>vecini; //liste de adiacenta in care stochez si lungimea

	vecini.resize(noduri + 1);

	for (int i = 0; i < muchii; i++)
	{
		int x, y, cost;

		f >> x >> y >> cost;

		vecini[x].push_back(make_pair(y, cost));
	}

	vector<int>d; // vector in care este stocat costul minim al unui drum de la start la u, descoperit pana la acel moment
	priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>>q; // coada de prioritati in care salvez nodurile neselectate inca

	d.resize(noduri + 1, 1000000);

	Dijkstra(1, vecini, d, q);

	for (int i = 2; i <= noduri; i++)
		if (d[i] == 1000000)
			o << 0 << " ";
		else
			o << d[i] << " ";
}

bool Graf::Bellman_Ford(int start, vector<vector<pair<int, int>>>& vecini, vector<int>& d)
{
	queue<int>q; // coada pentru varfurile ale caror eticheta s-a actualizat
	vector<bool>in_q(noduri + 1, 0);
	vector<int>contor(noduri + 1, 0); // verificam de cate ori a fost relaxat un varf

	d[start] = 0;
	q.push(start);
	in_q[start] = 1;

	while (!q.empty())
	{
		int u = q.front();
		q.pop();
		in_q[u] = 0;

		for (auto i = vecini[u].begin(); i != vecini[u].end(); i++)
		{
			int v = i->first;
			int cost = i->second;

			if (d[v] > d[u] + cost)
			{
				d[v] = d[u] + cost;

				if (in_q[v] == 0)
				{
					q.push(v);
					in_q[v] = 1;
					contor[v]++;
					if (contor[v] > noduri) // am gasit un ciclu negativ
						return 0; 
				}
			}
		}

	}

	return 1;
}

void Graf::solve_Bellman_Ford(ifstream& f, ofstream& o)
{
	vector<vector<pair<int, int>>>vecini(noduri + 1); //liste de adiacenta in care stochez si costul

	for (int i = 0; i < muchii; i++)
	{
		int x, y, cost;

		f >> x >> y >> cost;

		vecini[x].push_back(make_pair(y, cost));
	}

	vector<int>d(noduri + 1, 1000000); // vector in care este stocat costul minim al unui drum de la start la u, descoperit pana la acel moment

	if (Bellman_Ford(1, vecini, d))
		for (int i = 2; i <= noduri; i++)
			cout << d[i] << " ";
	else
		cout << "Ciclu negativ!";
}

int main()
{
	int problema;

	problema = 8;

	if (problema == 1) //BFS - Parcurgere in latime
	{
		ifstream f("bfs.in");
		ofstream o("bfs.out");

		int noduri, muchii;

		f >> noduri >> muchii;

		Graf g(noduri, muchii);

		g.solve_bfs_distanta_minima(f, o);
	}

	else if (problema == 2) // Parcurgere DFS - componente conexe
	{
		ifstream f("dfs.in");
		ofstream o("dfs.out");

		int noduri, muchii;

		f >> noduri >> muchii;

		Graf g(noduri, muchii);

		g.solve_componente_conexe(f, o);
	}

	else if (problema == 3) // Sortare topologica
	{
		ifstream f("sortaret.in");
		ofstream o("sortaret.out");

		int noduri, muchii;

		f >> noduri >> muchii;

		Graf g(noduri, muchii);

		g.solve_sortare_topologica(f, o);

	}

	else if (problema == 4) // Componente tare conexe
	{
		ifstream f("ctc.in");
		ofstream o("ctc.out");

		int noduri, muchii;

		f >> noduri >> muchii;

		Graf g(noduri, muchii);

		g.solve_componente_tare_conexe(f, o);
	}

	else if (problema == 5) // Paduri de multimi disjuncte
	{
		ifstream f("disjoint.in");
		ofstream o("disjoint.out");

		int noduri;

		f >> noduri;

		Disjoint_set g(noduri);

		g.solve_paduri_de_multimi_disjuncte(f, o);
	}

	else if (problema == 6) // Arbore partial de cost minim
	{
		ifstream f("apm.in");
		ofstream o("apm.out");

		int noduri, muchii;

		f >> noduri >> muchii;

		Graf g(noduri, muchii);

		g.solve_arbore_partial_de_cost_minim_Kruskal(f, o);

	}

	else if (problema == 7) // Algoritmul lui Dijkstra
	{
		ifstream f("dijkstra.in");
		ofstream o("dijkstra.out");

		int noduri, muchii;

		f >> noduri >> muchii;

		Graf g(noduri, muchii);

		g.solve_Dijkstra(f, o);
	}

	else if (problema == 8) // Algoritmul Bellman-Ford
	{
		ifstream f("bellmanford.in");
		ofstream o("bellmanford.out");

		int noduri, muchii;

		f >> noduri >> muchii;

		Graf g(noduri, muchii);

		g.solve_Bellman_Ford(f, o);

	}
	return 0;
}