Problem
景点“知识迷宫”建于暑期计算机学校 (LCS)。迷宫由 N 个房间组成，编号从 1 到 N，其中一些房间之间有门。当一个人穿过一扇门时，他的知识指标会发生一定量的变化，这个量是为这扇门固定的。迷宫的入口在 1 号房间，出口在 1 号房间。在 N 房间。每个学生恰好穿过迷宫一次，并根据获得的知识量进入一个或另一个学习组（进入迷宫时，该指标为零）。你的任务是展示最好的结果。
输入：
输入的第一行包含整数 N (1 <= N <= 2000) –房间数和 M (1 <= M <= 10000) –门的数量。接下来的 M 行中的每一行都包含对门的描述——它通向的房间数和通向的房间数（你只能朝一个方向穿过门），以及穿过门时加到知识量上的一个整数（这个数字不超过 10000 的模数）。门可以从一个房间通向它自己，两个房间之间可以有不止一扇门。
输出：
显示“:)” –如果你能获得无限量的知识，":(" –如果迷宫无法通过，否则获得的知识量最大。
例子
<头>
<日>#
| 输入 |
输出 |
<正文>
| 1 |
2 2
1 2 3
1 2 7
|
7 |