描述

为了缓解沉重的学习压力,某任姓工厂决定通过刷题来获得快乐

他刷的题很多(什么必刷题啊,一遍过啊,五三啊,金考卷啊数不胜数)

为了方便我们给练习册从1到n编号

当他从第u本练习册做到v时会获得w的快乐

这样获得快乐的途径有m种

当然这些快乐是以乘积积累

他一上瘾便只会沿着一条途径刷下去

现在他等着快乐，不想思考这个问题了

便交给你了

输入格式

第一行两个个整数n,m

接下来m行,每行3个整数u,v,w,分别表示起点,终点,权值

输出格式

一行一个整数x表示某任姓工厂从1到n的最“小”快乐值

样例输入

3 3
1 2 3
2 3 3
1 3 10

样例输出

9

时间限制

每个测试点3s (我的程序本机均在1.6s以内)

注释 Hint

对于10%的数据,保证输入为一棵树

对于另外10%的数据有n<=100

对于100%的数据有n<=2x10^5,m<=4x10^6,w<=1000