Untitled

You are given a directed graph with V vertices and E edges. Some edges may have negative weights. Your task is to determine which node is used the most across all shortest paths between every pair of nodes, and output both the node and the number of times it is used.

In this problem, a node is considered used if it is a part of the shortest path between any pair of nodes.

Input: The first line contains two integers V (number of vertices) and E (number of edges).

The next E lines contain three integers u, v, and w, representing a directed edge from node u to node v with weight w.

Output:Output two integers: The node that is used the most times across all shortest paths, The number of times this node is used in the shortest paths. If multiple nodes are used the same maximum number of times, return the

smallest node.

Input

Output

57

37

016

027

135

23-10

14-2

34-1

202