这类的题目据说很常见，但是我几乎从来没有遇到过。

是很神奇的一道题呢！

必须要经过 $d_i$ 条边才能走第 $i$ 条边，求从 $1$ 到 $n$ 的最少经过的边的数量。

图论中的矩阵优化

先上一个预备知识，就是图论中的矩阵优化。

众所周知，矩阵描述的是一种变换，而只要满足结合律，就可以进行快速幂，所以可以用快速幂来快速的求出一些变换以后的结果。

如这样一道题：

求 $S$ 到 $E$ 经过 $k$ 条边的最短路。

我们可以用矩阵来描述原来的边，然后重新定义一下矩阵乘法成下面的样子，这样就相当于用走一次一个矩阵所代表的边，另一个矩阵新的最短路情况。

twt operator * (twt b) {
	twt c;
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= n; j++)
			for(int k = 1; k <= n; k++)
				c[i][j] = std::min(a[i][k] + b[k][j], c[i][j]);
	return c;
}

这样的话，自己乘上自己就相当于当前这个图每个点走一次的多源最短路情况，所以在这题中，我们只需要将它乘 $k$ 次就可以了。

回到本题

然后再回到这一题中来。

首先为了消除 $d$ 的影响，我们可以按照 $d$ 从小到大去遍历所有的边。

然后先把原来图的连通性进行若干次变换，相当于走了当前的 $d$ 这一边了。然后就可以走这条边了，所以接着将这条边加入到描述连通性的矩阵中去，通过一个多源 bfs 找到现在的最短路(因为边权都是 $1$ 所以不需要 Dijkstra)。

然后更新一次答案，继续重复直到当前的 $d$ 比 $ans$ 还大就可以退出了。

此题需要 bitset 优化。然后代码里实现有一个小的细节，因为 $1 \times n$ 的矩阵和 $n \times n$ 的矩阵相乘的时候把 bitset 竖起来不方便，所以直接把连通性反着存进去，这样就不需要处理这个情况了。

代码。

#include <cstdio>
#include <bitset>
#include <queue>
#include <algorithm>
#define int long long
const int N = 155, M = N, INF = 2000000000;
typedef std::bitset<N> bitset;
bitset v;
int n, m, ans = INF, d[N];
struct cmf {
	int u, v, d;
	bool operator < (cmf b) const {
		return d < b.d;
	}
} e[M];
struct twt {
	bitset a[N];
	friend bitset operator * (bitset x, twt y) {
		bitset z;
		for(int i = 1; i <= n; i++) z[i] = (x&y[i]).any();
		return z;
	}
	friend twt operator * (twt x, twt y) {
		twt z;
		for(int i = 1; i <= n; i++)
			for(int j = 1; j <= n; j++)
				if(x[i][j]) z[i] |= y[j];
		return z;
	}
	bitset& operator [] (int x) { return a[x]; }
} a;
void Pow(bitset &z, twt x, int y) {
	while(y) {
		if(y & 1) z = z * x;
		x = x * x;
		y >>= 1;
	}
}
signed main() {
	scanf("%lld%lld", &n, &m);
	for(int i = 1; i <= m; i++) scanf("%lld%lld%lld", &e[i].u, &e[i].v, &e[i].d);
	std::sort(e+1, e+1+m);
	v[1] = 1;
	for(int i = 1, t = 0; i <= m; i++) {
		if(e[i].d >= ans) break;
		int o = e[i].d - t;
		Pow(v, a, o);
		a[e[i].v][e[i].u] = 1;
		t = e[i].d;
		std::queue<int> q;
		for(int x = 1; x <= n; x++)
			if(v[x]) q.push(x), d[x] = 0;
			else d[x] = INF;
		while(!q.empty()) {
			int u = q.front(); q.pop();
			for(int v = 1; v <= n; v++) 
				if(a[v][u] && d[v] == INF)
					d[v] = d[u] + 1, q.push(v);
		}	
		ans = std::min(ans, t + d[n]);
	}
	if(ans == INF) puts("Impossible");
	else printf("%lld", ans);
	return 0;
}