UOJ Logo 黑暗爆炸OJ

DARKBZOJ

Statistics

Description

cwbc最近在研究无向图,他想要在一个点数为n、边数为m的无向图中找到一个最大的边独立集,但他觉得这样不够
有趣,于是他给每条边一个边权wi,在保证边独立集边数最多的情况下,要求最大权值与最小权值的差最小,但是
cwbc太弱了,只好请大家来帮忙。

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

第一行一个整数,表示最大边独立集的边数。
第二行一个整数,表示题目要求的最小差值。

Sample Input

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

Sample Output

2
4

Hint

Source

By cwbc