该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

小贝探索一片古代遗迹，遗迹由若干石室与通道构成。石室之间由双向通道相连，部分通道存在封印，无法通行。小贝从起始石室出发，想要前往目标石室。你需要先搭建遗迹的通道关系，再利用搜索算法求解。

题目描述

给定一张无向图： 一共有 N 个石室，编号 $1 \sim N$ M 条双向通道，每条通道连接两个石室。 每条通道拥有一个状态：0=正常可通行，1=封印封锁，不能经过。 给定起点 S、终点 T。

求出从 S 走到 T 的最少经过通道数量；若无法到达，输出 -1。

输入格式

第一行两个整数 $N,M$：石室数量、通道数量。 接下来 M 行，每行三个整数 $u,v,w$ $u,v$：通道连接的两个石室；$w=0$开放 / $w=1$封印。 最后一行两个整数 $S,T$，起点、终点石室编号。

输出格式

输出一行整数：从 S 到达 T 经过通道的最小数目；不可达输出 -1。

6 7
1 2 0
1 3 1
2 4 0
2 5 0
3 5 0
4 6 1
5 6 0
1 6

3

数据范围与提示

$1 \le N \le 100,\quad 0\le M \le 200$ $1\le S,T \le N$