Description

cwbc最近在研究无向图，他想要在一个点数为n、边数为m的无向图中找到一个最大的边独立集，但他觉得这样不够

有趣，于是他给每条边一个边权wi，在保证边独立集边数最多的情况下，要求最大权值与最小权值的差最小，但是

cwbc太弱了，只好请大家来帮忙。

Format

Input

第一行两个正整数n、m，n为点数，m为边数。

接下来m行，每行三个正整数xi、yi、wi，表示xi与yi之间有一条边权为wi的无向边。

1<=n<=120, 1<=m<=n*(n-1)/2, 1<=wi<=10^9, 保证不存在重边和自环

Output

第一行一个整数，表示最大边独立集的边数。

第二行一个整数，表示题目要求的最小差值。

Samples

4 4
1 2 1
3 4 7
2 3 2
1 4 6

2
4