题目描述

给出一张 $n$ 个点，$m$ 条边的的有向图。设 $f(s,t,k)$ 表示从点 $s$ 到点 $t$，只经过点 $1$ 到 $k$ 以及 $s,t$ 的最短路径，如果不存在则为 $0$。

你需要求出以下式子的值：

输入格式

第一行两个数 $n,m$。

接下来 $m$ 行，每行三个数 $u_i,v_i,w_i$，表示一条从 $u_i$ 到 $v_i$，权值为 $w_i$ 的单向边。

Translated by _Ponder_