/*
#include<iostream>
#include<cstdio>
#include<vector>
#include<queue>
#include<deque>
#include<list>
#include<stack>
using namespace std;

const int inf = INT_MAX;

int n, m;
vector<int> graph[1024];
bool used[1024];

// BFS, finding shortest path between two specified vertexes
void BFS(int x, int dest)
{
	used[x] = true;
	queue<int> q;
	q.push(x);
	int fr;

	vector<int> parents;
	vector<int> vertexes;

	parents.push_back(x);
	vertexes.push_back(x);

	bool exited = false;

	while (!q.empty())
	{
		fr = q.front();
		q.pop();
		printf("%d ", fr);

		for (int i = 0; i < graph[fr].size(); i++)
		{
			if (used[graph[fr][i]] == false)
			{
				parents.push_back(fr);
				vertexes.push_back(graph[fr][i]);

				if (graph[fr][i] == dest)
				{
					exited = true;
					break;
				}
				q.push(graph[fr][i]);
				used[graph[fr][i]] = true;
			}
		}

		if (exited) break;
	}

	list<int> path;
	int i = parents.size() - 1;
	int target = parents[i];
	path.push_front(vertexes[i]);
	i--;

	while (i >= 0)
	{
		if (vertexes[i] != target)
		{
			i--;
		}
		else
		{
			path.push_front(target);
			target = parents[i];
			i--;
		}
	}

	printf("\n");

	for (auto it = path.begin(); it != path.end(); it++)
	{
		printf("%d ", *it);
	}
	printf("\n");
}

// graph coloring
// 0 - not visited
// 1 - painted red
// 2 - painted blue
int colors[1000];
void BFSColor(int x)
{
	queue<int> q;
	q.push(x);
	colors[x] = 1;
	int fr;

	bool exited = false;

	while (!q.empty())
	{
		fr = q.front();
		//printf("%d ", fr);
		q.pop();

		int nextColor = (colors[fr] == 1) ? 2 : 1;

		for (int i = 0; i < graph[fr].size(); i++)
		{
			if (colors[graph[fr][i]] == 0)
			{
				colors[graph[fr][i]] = nextColor;
				q.push(graph[fr][i]);
			}
			else if (colors[graph[fr][i]] == 1)
			{
				if (colors[fr] == 1)
				{
					printf("It is not bipartite!\n");
					exited = true;
					break;
				}
			}
			else if (colors[graph[fr][i]] == 2)
			{
				if (colors[fr] == 2)
				{
					printf("It is not bipartite!\n");
					exited = true;
					break;
				}
			}
		}
		if (exited) break;
	}
	if (!exited) printf("It is bipartite!\n");
}

// topological sorting (for DAGs)
stack<int> topologicalSorting;
void DFSTopological(int x)
{
	used[x] = true;
	for (int i = 0; i < graph[x].size(); i++)
	{
		if (used[graph[x][i]] == false)
		{
			DFSTopological(graph[x][i]);
		}
	}
	topologicalSorting.push(x);
}

// puskame go za grafi, koito zapochvat ot vruh 1, lesno moje da se modificira i za grafi ot vruh 0
void topologialSort(int x)
{
	for (int i = 0; i < n; i++)
	{
		if (used[i] == false)
		{
			DFSTopological(i);
		}
	}

	while (!topologicalSorting.empty())
	{
		printf("%d ", topologicalSorting.top());
		topologicalSorting.pop();
	}
}

// modified DFS for SCC algrithm
stack<int> forSCC;
void DFS(int x, bool arrOfUsed[], vector<int> enterGraph[], bool flag)
{
	arrOfUsed[x] = true;

	for (int i = 0; i < enterGraph[x].size(); i++)
	{
		if (arrOfUsed[enterGraph[x][i]] == false)
		{
			DFS(enterGraph[x][i], arrOfUsed, enterGraph, flag);
		}
	}

	if (flag == true)
	{
		forSCC.push(x);
	}
}

vector<int> reversedGraph[1024];
bool usedReversed[1024];

int SCC (int x) // works, mind the starting vertex of a graph (0 or 1) !!!
{
	bool flag = true;
	DFS(x, used, graph, flag);

	for (int i = 1; i <= n; i++) // from vertex 1
	{
		for (int j = 0; j < graph[i].size(); j++)
		{
			reversedGraph[graph[i][j]].push_back(i);
		}
	}

	int counter = 0;
	flag = false;

	while (!forSCC.empty())
	{
		if (usedReversed[forSCC.top()] == false)
		{
			DFS(forSCC.top(), usedReversed, reversedGraph, flag);
			counter++;
			forSCC.pop();
		}
		else
		{
			forSCC.pop();
		}
	}

	return counter;
}

vector<pair<int, int>> graphW[1024];
bool usedW[1024];

void zeroOneBFS(int sourceVertex)
{
	vector<int> d(n + 1, inf);
	deque<int> q;

	d[sourceVertex] = 0;
	q.push_front(sourceVertex);
	int fr;

	while (!q.empty())
	{
		fr = q.front();
		q.pop_front();

		for (int i = 0; i < graphW[fr].size(); i++)
		{
			int u = graphW[fr][i].first;
			int w = graphW[fr][i].second;

			if (d[fr] + w < d[u])
			{
				d[u] = d[fr] + w;
				if (w == 1)
				{
					q.push_back(u);
				}
				else
				{
					q.push_front(u);
				}
			}
		}
	}

	for (int i = 2; i <= n; i++)
	{
		cout << "Shortest distance from " << 1 << " to " << i << " is " << d[i] << '\n';
	}
}

struct comp
{
	bool operator() (pair<int, int> p1, pair<int, int> p2)
	{
		return p1.second > p2.second;
	}
};

int dist[1024];
// yay, managed to implement it correctly
void dijkstra(int source, bool flag)
{
	priority_queue<pair<int, int>, vector<pair<int, int>>, comp> q;
	q.push({ source, 0 });

	pair<int, int> fr;

	while (!q.empty())
	{
		fr = q.top();
		q.pop();

		int vert = fr.first;
		int w = fr.second;

		if (dist[vert] != w)
		{
			continue;
		}

		for (int i = 0; i < graph[vert].size(); i++)
		{
			if (dist[graphW[vert][i].first] > dist[vert] + graphW[vert][i].second)
			{
				dist[graphW[vert][i].first] = dist[vert] + graphW[vert][i].second;

				q.push({ graphW[vert][i].first, dist[graphW[vert][i].first] });
			}
		}
	}
}

// Yay,Bellman-Ford works
struct edge
{
	int a, b, cost;
};

vector<edge> edges;
int distances[1000];

void bellman_ford(int numVertexes, int numEdges)
{
	edge e;
	for (int i = 0; i < numEdges; i++)
	{
		scanf("%d %d %d", &e.a, &e.b, &e.cost);
		edges.push_back(e);
	}

	for (int i = 2; i <= numVertexes; i++)
	{
		distances[i] = inf;
	}

	distances[1] = 0;
	int counter = 0;

	while (true)
	{
		bool change = false;

		for (int j = 0; j < numEdges; j++)
		{
			if (distances[edges[j].a] < inf)
			{
				if (distances[edges[j].b] > distances[edges[j].a] + edges[j].cost)
				{
					distances[edges[j].b] = distances[edges[j].a] + edges[j].cost;
					change = true;
				}
			}
		}

		if (distances[1] < 0)
		{
			cout << "Negative cycle detected!\n";
			return;
		}

		counter++;

		if (counter == numVertexes && change)
		{
			cout << "Negative cycle detected!\n";
			return;
		}

		if (change == false) break;
	}


	for (int i = 1; i <= numVertexes; i++)
	{
		cout << "Shortes path from vertex 1 to vertex " << i << " is " << distances[i] << '\n';
	}
}


// Yay, it works
int floydMatrix[1000][1000];

void floyd_warshall(int numVertexes, int numEdges)
{
	for (int i = 1; i <= numVertexes; i++)
	{
		for (int j = 1; j <= numVertexes; j++)
		{
			floydMatrix[i][j] = inf;
		}
	}

	int from, to, weight;
	for (int i = 0; i < numEdges; i++)
	{
		scanf("%d %d %d", &from, &to, &weight);
		floydMatrix[from][to] = weight;
	}

	int i = 1, j = 1;

	while (i <= numVertexes && j <= numVertexes)
	{
		floydMatrix[i][j] = 0;
		i++;
		j++;
	}

	for (int k = 1; k <= numVertexes; k++)
	{
		for (int i = 1; i <= numVertexes; i++)
		{
			for (int j = 1; j <= numVertexes; j++)
			{
				if (floydMatrix[i][k] < inf && floydMatrix[k][j] < inf)
				{
					floydMatrix[i][j] = min(floydMatrix[i][j], floydMatrix[i][k] + floydMatrix[k][j]);
					if (i == j && floydMatrix[i][j] < 0)
					{
						cout << "Negative cycle detected!\n";
						return;
					}
				}
			}
		}
	}

	for (int i = 1; i <= numVertexes; i++)
	{
		cout << "Shortest distance from vertex " << i;

		for (int j = 1; j <= numVertexes; j++)
		{
			cout << " to vertex " << j << " is: " << floydMatrix[i][j] << '\n';
		}

		cout << '\n';
	}
}

struct compInt
{
	bool operator()(pair<int, int> p1, pair<int, int> p2)
	{
		return p1.second > p2.second;
	}
};

// moje bi raboti, da go testvam
// trqbva da dobavq i bulev masiv na posetenite vurhove, za da znam koi sa poseteni i da ne zatvorq cikul

int n, m;
vector<pair<int, int>>graph[10024];
bool used[10024];

struct comp
{
	bool operator()(pair<int, int> p1, pair<int, int> p2)
	{
		return p1.second > p2.second;
	}
};

vector<pair<int, int>> rebraMST;

int prim(int source)
{
	priority_queue<pair<int, int>, vector<pair<int, int>>, comp> pq;
	pq.push({ source, 0 });
	pair<int, int> fr;

	int MSTWeight = 0;
	int counter = -1;

	vector<pair<int, int>> rebraMST;

	while (!pq.empty())
	{
		fr.first = pq.top().first;
		fr.second = pq.top().second; pq.pop();

		if (used[fr.first]) continue;
		used[fr.first] = true;

		MSTWeight += fr.second;
		counter++;

		if (counter == n - 1) return MSTWeight;

		int minWeightEdge = INT_MAX;
		int secondVert = -1;

		for (int i = 0; i < graph[fr.first].size(); i++)
		{
			if (used[graph[fr.first][i].first] == false)
			{
				pq.push({ graph[fr.first][i].first, graph[fr.first][i].second });
			}
		}
	}

	return MSTWeight;
}


int main()
{
	scanf("%d %d", &n, &m);
	int x, y, w;

	for (int i = 0; i < m; i++)
	{
		scanf("%d %d %d", &x, &y, &w);
		graphW[x].push_back(make_pair(y, w));
		graphW[y].push_back(make_pair(x, w));
	}

	//floyd_warshall(n, m);

	//BFS(2, 4); // na puviq red dave BFS obhojdane, koeto ne e korektno, zshtoto prekratqvam algorituma predsrochno, za da e korekten namereniq minimalen put
	//BFSColor(1);
	//topologialSort(1);
	//zeroOneBFS(1);

	system("pause");
	return 0;
}
*/