Harry Potter is going to have an exam. He needs your help. This course is about the ability to change one animal into another with a magic spell. For example, the spell to turn a cat into a mouse is haha, the spell to turn a mouse into a fish is hehe, and so on. A spell that changes in the opposite direction is simply to recite the original spell upside down. For example, ahah can turn a mouse into a cat. In addition, if you want to turn a cat into a fish, you can read a direct magic spell lalala, or you can connect the magic spells of cat into mouse and mouse into fish: hahahehe.

Now Harry Potter has a textbook in his hand, which lists all the deformation spells and animals that can change. The teacher allowed him to take an animal to the examination room to examine his ability to turn the animal into any designated animal. So he asked you: what animal can you take to make the most difficult animal (that is, the animal needs the longest spell to become the animal brought by Harry Potter himself) need the shortest spell? For example, if there are only cats, rats and fish, it is obvious that Harry Potter should take rats, because rats only need to read four characters to become two other animals; If you take a cat, you need to read at least 6 characters to turn the cat into a fish; Similarly, taking fish is not the best choice.

Input format:

Input Description: input line 1 to give two positive integers N (≤ 100) and m, where N is the total number of animals involved in the test and M is the number of magic spells used for direct deformation. For simplicity, we number the animals by 1~N. Then, in line m, each line gives three positive integers, which are the numbers of the two animals and the length of the spell required for deformation between them (≤ 100), and the numbers are separated by spaces.

Output format:

Output the number of the animal Harry Potter should take to the examination room and the length of the longest deformation spell, separated by a space. If it is impossible to complete all deformation requirements with only 1 animal, output 0. If several animals can be selected, the one with the lowest number will be output.

Input example:

6 11
3 4 70
1 2 1
5 4 50
2 6 50
5 6 60
1 3 70
4 6 60
3 6 80
5 1 100
2 4 60
5 2 80

No blank lines at the end

Output example:

4 70

No blank lines at the end

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;
const int MAXN = 110;
struct info{
	int net[MAXN][MAXN],N,E;
}Graph;
void dijkstra(info &a,vector<int> &path,vector<int> &dist,int v0)
{
	int n = a.N,V;
	vector<int> flag(n+1,0);//sign 
	for(int i = 1;i <= n;i++){
		if(a.net[v0][i] > 0){
			dist[i] = a.net[v0][i];
			path[i] = v0;
		}
	}
	dist[0] = -1;
	dist[v0] = 0;
	flag[v0] = 1;
	path[v0] = 0;
	for(int i = 1;i < n;i++){
		int MIN = INT_MAX;
		for(int j = 1;j <= n;j++){
			if(flag[j] == 0 && dist[j] < MIN){
				V = j;
				MIN = dist[j];
			}
		}
		flag[V] = 1;
		for(int j = 1;j <= n;j++){
			if(flag[j] == 0 && a.net[V][j] > 0 && dist[j] > dist[V]+a.net[V][j]){
				dist[j] = dist[V] + a.net[V][j];
				path[j] = V;
			}
		}
	}
}
bool clear(vector<int> &a)
{
	int n = a.size();
	for(int i = 1;i < n;i++){
		if(a[i] == INT_MAX) return false;
		else a[i] = INT_MAX;
	}
	return true;
}
int main()
{
	int n1,n2,w;
	scanf("%d %d",&Graph.N,&Graph.E);
	for(int i = 0;i < Graph.E;i++){
		scanf("%d %d %d",&n1,&n2,&w);
		Graph.net[n1][n2] = Graph.net[n2][n1] = w;
	}
	vector<int> path(Graph.N+1,-1),dist(Graph.N+1,INT_MAX);
	int min = INT_MAX,minv,flag = 1;
	for(int i = 1;i <= Graph.N;i++){
		dijkstra(Graph,path,dist,i);
		sort(dist.begin(),dist.end(),greater<int>());
		if(*dist.begin() < min){
			min = *dist.begin();
			minv = i;
		}
		if(!clear(dist)){
			flag = 0;
			break;
		}
	}
	if(flag) printf("%d %d",minv,min);
	else printf("0");
	return 0;
}