题目描述

给定一个$n$个点$m$条边的有向图, 图中可能存在重边和自环, 边权可能为负数

请你求出$1$号点到$n$号点的最短距离, 如果无法从$1$号点走到$n$号点或者从$1$到$n$的路径上存在负权回路, 则输出$impossible$

样例输入

第一行包含两个整数$n, m$

接下来$m$行, 每行包含三个整数$x, y, z$, 表示存在一条从点$x$到点$y$的有向边, 边长为$z$

点的编号从$1$到$n$

样例输出

输出一个整数, 表示从$1$号点到$n$号点的最短距离

如果不存在满足条件的路径, 则输出$impossible$

样例

样例一

3 3
1 2 1
2 3 1
1 3 3

2

数据范围

$1 \le n \le 10^{4}$

$1 \le m \le 1.5 * n$

任意边长的绝对值不能超过$10^{4}$