/*
            整体思路：区间DP
                      这题首先我们可以发现它的一个性质：
                            题目数据给出的是一个环
                      那么，我们直接断环成链，复制两遍
                      然后，求最大值的话，用DP肯定是十分方便的
                      设计一个状态表示，设f[i][j][0/1]分别表示
                      i ~ j这一段分别合并之后的最大值、最小值
                      这里，诶，有的同学可能就要问了，为什么
                      还要存它的最小值呢，题目不是问的最大值吗？
                      这个问题很好，噢，我们考虑一下，它其实是有
                      可能有一个极端数据的，类似以下：
                            -39114514 * -1919810
                      所以又是只存最大值并不是最优解，于是就需
                      要最小值。
                      然后我们考虑状态转移方程。
                      根据状态设计与题目DP类型，我们应该是得出了
                      以下状态转移方程式：
                            f[i][j][0] = max{f[i][k][x] *|+(opt[k + 1] = '+'|'x') f[k + 1][j][y]}(i <= k < j)
                            f[i][j][1] = min{f[i][k][x] *|+(opt[k + 1] = '+'|'x') f[k + 1][j][y]}(i <= k < j)
                      于是，在求出答案后，再根据转态转移方程求出方案就行了
                      刚看到这题感觉还是简单的呀，怎么一写就过去了这么久~~（大概39min）~~  ~~可惜代码注释不能用Katex~~
                      这题是一个区间DP比较模板的题了，有枚举断点，不像求什么区间回文子序列那样的
*/
#include <bits/stdc++.h>

using namespace std;

const int N = 110;

int n;
char opt[N];//符号
int g[N];//数
int f[N][N][2];//区间DP方程状态表示设计
int res, path[N << 1];//答案数组方案

int calc(int a, int b, char opt)
{
    if (opt == 'x') return a * b;
    return a + b;//根据符号求值
}

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i ++ )
    {
        cin >> opt[i] >> g[i];
        opt[i + n] = opt[i];
        g[i + n] = g[i];//断环成链，复制两遍
    }

    for (int i = 1; i <= 2 * n; i ++ )
        for (int j = 1; j <= 2 * n; j ++ )
        {
            if (i == j) f[i][j][0] = f[i][j][1] = g[i];//初始化
            else f[i][j][0] = INT_MIN, f[i][j][1] = INT_MAX;//没求过，初始化
        }
    for (int len = 2; len <= n; len ++ )
        for (int l = 1; l <= 2 * n - len + 1; l ++ )
        {
            int r = l + len - 1;
            for (int k = l; k < r; k ++ )//枚举断点
                for (int x = 0; x < 2; x ++ )
                    for (int y = 0; y < 2; y ++ )
                    {
                        f[l][r][0] = max(f[l][r][0], calc(f[l][k][x], f[k + 1][r][y], opt[k + 1]));//区间DP
                        f[l][r][1] = min(f[l][r][1], calc(f[l][k][x], f[k + 1][r][y], opt[k + 1]));
                    }
        }
    path[0] = INT_MIN;//偷懒，利用废弃的path[0]
    for (int i = 1; i <= n; i ++ )
    {
        int t = f[i][i + n - 1][0];//当前最大值
        if (path[0] < t)
        {
            path[0] = t;
            path[res = 1] = i;//更新
        }
        else if (path[0] == t) path[ ++ res] = i;//加入当前答案
    }

    cout << path[0] << '\n';
    for (int i = 1; i <= res; i ++ ) cout << path[i] << ' ';//输出答案
    cout << '\n';

    return 0;
}

/*
            整体思路：区间DP
                      这题首先我们可以发现它的一个性质：
                            题目数据给出的是一个环
                      那么，我们直接断环成链，复制两遍
                      然后，求最大值的话，用DP肯定是十分方便的
                      设计一个状态表示，设f[i][j][0/1]分别表示
                      i ~ j这一段分别合并之后的最大值、最小值
                      这里，诶，有的同学可能就要问了，为什么
                      还要存它的最小值呢，题目不是问的最大值吗？
                      这个问题很好，噢，我们考虑一下，它其实是有
                      可能有一个极端数据的，类似以下：
                            -39114514 * -1919810
                      所以又是只存最大值并不是最优解，于是就需
                      要最小值。
                      然后我们考虑状态转移方程。
                      根据状态设计与题目DP类型，我们应该是得出了
                      以下状态转移方程式：
                            f[i][j][0] = max{f[i][k][x] *|+(opt[k + 1] = '+'|'x') f[k + 1][j][y]}(i <= k < j)
                            f[i][j][1] = min{f[i][k][x] *|+(opt[k + 1] = '+'|'x') f[k + 1][j][y]}(i <= k < j)
                      于是，在求出答案后，再根据转态转移方程求出方案就行了
                      刚看到这题感觉还是简单的呀，怎么一写就过去了这么久~~（大概39min）~~  ~~可惜代码注释不能用Katex~~
                      这题是一个区间DP比较模板的题了，有枚举断点，不像求什么区间回文子序列那样的
*/
#include <bits/stdc++.h>

using namespace std;

const int N = 110;

int n;
char opt[N];//符号
int g[N];//数
int f[N][N][2];//区间DP方程状态表示设计
int res, path[N << 1];//答案数组方案

int calc(int a, int b, char opt)
{
    if (opt == 'x') return a * b;
    return a + b;//根据符号求值
}

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i ++ )
    {
        cin >> opt[i] >> g[i];
        opt[i + n] = opt[i];
        g[i + n] = g[i];//断环成链，复制两遍
    }

    for (int i = 1; i <= 2 * n; i ++ )
        for (int j = 1; j <= 2 * n; j ++ )
        {
            if (i == j) f[i][j][0] = f[i][j][1] = g[i];//初始化
            else f[i][j][0] = INT_MIN, f[i][j][1] = INT_MAX;//没求过，初始化
        }
    for (int len = 2; len <= n; len ++ )
        for (int l = 1; l <= 2 * n - len + 1; l ++ )
        {
            int r = l + len - 1;
            for (int k = l; k < r; k ++ )//枚举断点
                for (int x = 0; x < 2; x ++ )
                    for (int y = 0; y < 2; y ++ )
                    {
                        f[l][r][0] = max(f[l][r][0], calc(f[l][k][x], f[k + 1][r][y], opt[k + 1]));//区间DP
                        f[l][r][1] = min(f[l][r][1], calc(f[l][k][x], f[k + 1][r][y], opt[k + 1]));
                    }
        }
    path[0] = INT_MIN;//偷懒，利用废弃的path[0]
    for (int i = 1; i <= n; i ++ )
    {
        int t = f[i][i + n - 1][0];//当前最大值
        if (path[0] < t)
        {
            path[0] = t;
            path[res = 1] = i;//更新
        }
        else if (path[0] == t) path[ ++ res] = i;//加入当前答案
    }

    cout << path[0] << '\n';
    for (int i = 1; i <= res; i ++ ) cout << path[i] << ' ';//输出答案
    cout << '\n';

    return 0;
}

/*
            整体思路：有向图的必经边、点 + topo（tarjan）
                      这放在tarjan的模块里，但实际上可以
                      用topoDP做，又为了让危险程度最小，
                      所以我们需要求最短路
                      然后求必经边的话，是要从S,T分别求
                      道路方案数的，于是这两个就用topoDP实现
                      运用Hash的思想，我们选择一个大质数
                      1e9 + 7，用来模，防止数据过大
                      然后在最短路上用双指针枚举，求出从 
                      S 到最短路上的第 i 个节点只搭一次车
                      的最小危险程度ds[],再求出从最短路上第 
                      i 个节点到 T 只搭一次车的最小危险程度
                      dt[],枚举每个点，用ds[i] + dt[i]更新答案
                      但是，还有一种情况，我们没有考虑，那就是
                      将两段乘车的路程连在一起，其实也很好解决
                      在双指针一次，比最小值就行了
*/
#include <bits/stdc++.h>//万能头

using namespace std;

typedef long long LL;

const int N = 1e5 + 10, M = N * 4, MOD = 1e9 + 7;//MOD用来放置数据过大

int n, m;
int h[N], e[M], ne[M], w[M], idx;//边数组
int p[N], q[N];//队列，与路上倒退用的存边数组
LL din[N][2], f[N][2];//方案数f[][0/1]与入度din[][0/1]0为正向边，1为反向边
LL ds[M], dt[M];//开头注释提到的
LL sum[M], sum_bri[M];//前缀和
bool is_bri[M];//每条边是否为毕竟边
int s, t, Q;
LL dist[N];//最短路
LL a[M], b[M], cnt;

void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;//加边
}

void init()
{
    memset(h, -1, sizeof h);
    memset(ds, 0, sizeof ds);
    memset(dt, 0, sizeof dt);
    memset(is_bri, 0, sizeof is_bri);//初始化
    memset(f, 0, sizeof f);
    memset(din, 0, sizeof din);
    idx = cnt = 0;
}

void topo(int u, int type)
{
    if (!type)
    {
        memset(dist, 0x3f, sizeof dist);//是否求最短路
        dist[u] = 0;
    }
    int hh = 0, tt = -1;
    for (int i = 1; i <= n; i ++ )
        if (!din[i][type]) q[ ++ tt] = i;//入队

    f[u][type] = 1;//方案数

    while (hh <= tt)
    {
        auto tp = q[hh ++ ];//取出队头

        for (int i = h[tp]; ~i; i = ne[i])
        {
            if ((i & 1) != type) continue;//同向边
            int j = e[i];

            (f[j][type] += f[tp][type]) %= MOD;//方案数更新

            if (!type && dist[j] > dist[tp] + w[i])//最短路
            {
                dist[j] = dist[tp] + w[i];
                p[j] = i;//路径
            }

            if ( -- din[j][type] == 0) q[ ++ tt] = j;//入队
        }
    }
}

int main()
{
    int T;
    cin >> T;
    while (T -- )//多组数据
    {
        init();//初始化
        cin >> n >> m >> s >> t >> Q;
        s ++ , t ++ ;//节点从1开始
        while (m -- )
        {
            int a, b, c;
            cin >> a >> b >> c;
            a ++ , b ++ ;
            add(a, b, c), add(b, a, c);//加边
            din[b][0] ++ ;//正向边入度
            din[a][1] ++ ;//反向边入度
        }

        topo(s, 0);//正向DP
        if (!f[t][0])
        {
            cout << "-1\n";//无法到达
            continue;
        }
        topo(t, 1);//反向DP

        for (int i = 0; i < idx; i += 2)
        {
            int x = e[i ^ 1], y = e[i];
            if (f[x][0] * f[y][1] % MOD == f[t][0]) //枚举正向边，记录是否必经
                is_bri[i] = is_bri[i ^ 1] = true;
        }
        int y = t;
        while (y != s)
        {
            a[ ++ cnt] = w[p[y]];
            b[cnt] = is_bri[p[y]];
            y = e[p[y] ^ 1];//倒推，记录
        }

        reverse(a + 1, a + 1 + cnt);//翻转
        reverse(b + 1, b + 1 + cnt);
        for (int i = 1; i <= cnt; i ++ )
        {
            sum[i] = sum[i - 1] + a[i];
            sum_bri[i] = sum_bri[i - 1] + (b[i] ? a[i] : 0);//求前缀
        }
        for (int i = 1, j = 0; i <= cnt; i ++ )
        {
            while (sum[i] - sum[j] > Q) j ++ ;
            ds[i] = ds[i - 1] + (b[i] ? a[i] : 0);
            LL tmp = sum_bri[j];//双指针求ds
            if (b[j]) tmp -= Q - sum[i] + sum[j];
            ds[i] = min(ds[i], tmp);
        }
        for (int i = cnt, j = cnt + 1; i; i -- )
        {
            while (sum[j - 1] - sum[i - 1] > Q) j -- ;
            dt[i] = dt[i + 1] + (b[i] ? a[i] : 0);
            LL tmp = sum_bri[cnt] - sum_bri[j - 1];//双指针求dt
            if(b[j]) tmp -= Q - sum[j - 1] + sum[i - 1];
            dt[i] = min(dt[i], tmp);
        }
        LL res = LLONG_MAX;
        for (int i = 1; i <= cnt + 1; i ++ ) res = min(res, dt[i] + ds[i - 1]);//拼
        for (int i = 1, j = 0; i <= cnt; i ++ )
        {
            while (sum[i] - sum[j] > 2 * Q) j ++ ;
            LL tmp = sum_bri[j] + sum_bri[cnt] - sum_bri[i];
            if (b[j]) tmp -= 2 * Q - sum[i] + sum[j];//双指针处理连续做的情况
            res = min(res, tmp);
        }

        cout << res << '\n';//答案
    }

    return 0;
}

/*
            整体思路：暴力枚举
                      开始直接怀疑人生，再一眼数据范围
                      没事了，暴力
*/
#include <bits/stdc++.h>

using namespace std;

int main()
{
    int a, b, c;
    int T;
    cin >> T;
    while (T -- )
    {
        cin >> a >> b >> c;
        bool flg = 0;
        for (int i = 0; i <= 1000; i ++ )
            for (int j = 0; j <= 10000/*。多打了一个0,1000应该就够了*/; j ++ )//暴力
                if (i * a + j * b == c)//题目给的
                {
                    flg = true;//可行
                    break;
                }

        if (flg) puts("Yes");//答案
        else puts("No");
    }

    return 0;
}

/*
            整体思路：枚举
                      刚拿到手，先想到链式前向星
                      于是直接打完，后来发现很可恶的是
                      我对链式前向星求环不是很熟练
                      （是时候去补一补链式前向星求环了）
                      然后，发现数据范围才4000，果断改掉
                      变成用bool存边，然后暴力枚举较好了
*/
#include <bits/stdc++.h>

using namespace std;

const int N = 4010;

int n, m;
int edge[N];
bool st[N][N];

int main()
{
    cin >> n >> m;
    while (m -- )
    {
        int a, b;
        cin >> a >> b;
        st[a][b] = st[b][a] = true;
        edge[a] ++ , edge[b] ++ ;//加进边数
    }

    int res = 0x3f3f3f3f;
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= n; j ++ )
        {
            if (st[i][j] && i != j)//两点有边
            {
                for (int k = 1; k <= n; k ++ )
                    if (k != i && k != j && st[i][k] && st[j][k])//枚举第三个点是否有边
                        res = min(res, edge[i] + edge[j] + edge[k] - 6);//边数，[o（连最后一个点）--o--o（连第一个点）]
                        //发现它有2条边连2边的点，所以 - 2 * 3（个点）
            }
        }

    if (res == 0x3f3f3f3f) cout << -1 << '\n';//无解
    else cout << res << '\n';//答案

    return 0;
}

/*
            整体思路：埃氏筛法 + 分解质因数
                      这道题一拿到手，感觉不难，但是
                      细一看，好难，后来，我就想到这
                      题一定是与质数有关的，于是先打
                      一遍埃氏筛。然后没有头绪，分析
                      样例，发现和分解质因数肯定是有关的
                      然后看样例2，发现它提问又不是一倍
                      一倍增长的，于是想到幂，然后开始乱dei
                      dei了一通，再看一眼样例，又联系到
                      了之前想到的一个东西，就是分解质因数
                      我们发现不需要提问的数，肯定是能被以
                      提问的数分解的，所以只要取幂
                      就过了
*/
#include <bits/stdc++.h>

using namespace std;

const int N = 1010;

int n;
bool is_prime[N];
int res, path[N];
bool st[N];

void init()
{
    is_prime[1] = true;
    for (int i = 2; i <= 1e3; i ++ )
        if (!is_prime[i])
            for (int j = 2; j * i <= 1e3; j ++ )//埃氏筛法
                is_prime[i * j] = true;
}

int main()
{
    cin >> n;

    init();

    for (int i = 2; i <= n; i ++ )
    {
        if (!st[i] && !is_prime[i])//用质数向上遍历，并且已经干掉的不管
        {
            st[i] = true;//干掉它
            path[ ++ res] = i;
            for (int j = i; j * i <= n; j *= i)
                if (!st[i * j])
                {
                    path[ ++ res] = i * j;//平方搞进去
                    st[i * j] = true;//搞掉
                }
        }
    }

    cout << res << '\n';
    for (int i = 1; i <= res; i ++ )
        cout << path[i] << ' ';//答案

    return 0;
}

/*
                整体思路：树的直径
                          这题显然是要求树的直径的
                          然后按照题目的要求是要求直径
                          必须边的，大佬胡源浩用的是DP
                          我不会，我们就用朴素的办法
                          我们发现只要是必须边，肯定
                          是形成一条链的，因为假设有两段
                          边是必须边，那么如果中间的不是
                          就意味着那2段中是有其他边的，
                          那样就形成环了，就不符合树的定义了
*/
#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 10, M = N * 2;

typedef long long LL;

int n;
int h[N], e[M], ne[M], w[M], idx;
LL d[N];
int fa[N];
int q[M];
vector<int> path;
bool st[N];

void add(int a, int b, int c)
{
    e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx ++ ;
}

int bfs(int root)
{
    memset(fa, -1, sizeof fa);
    memset(d, -1, sizeof d);
    int hh = 0, tt = 0;
    q[0] = root;
    d[root] = 0;

    while (hh <= tt)
    {
        auto t = q[hh ++ ];

        for (int i = h[t]; ~i; i = ne[i])
        {
            int j = e[i];
            //求直径
            if (~d[j]) continue;
            d[j] = d[t] + w[i];
            fa[j] = i;
            q[ ++ tt] = j;
        }
    }

    int res = 0;
    for (int i = 1; i <= n; i ++ )
        if (d[res] < d[i]) res = i;

    return res;
}

void dfs(int u)
{
    st[u] = true;

    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (st[j]) continue;
        dfs(j);//求出最远距离
        d[u] = max(d[u], d[j] + w[i]); 
    }
}

int main()
{
    memset(h, -1, sizeof h);
    cin >> n;
    for (int i = 1; i < n; i ++ )
    {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c), add(b, a, c);
    }

    int p = bfs(1);//求直径
    int q = bfs(p);

    cout << d[q] << '\n';

    int y = q;
    path.push_back(q);
    while (y != p)
    {
        y = e[fa[y] ^ 1];
        path.push_back(y);
    }
    reverse(path.begin(), path.end());//找路，并反转

    memset(d, 0, sizeof d);
    for (int x : path) st[x] = true;
    for (int x : path) dfs(x);//更新

    int l = 0, r = path.size() - 1;
    LL tmp = 0;
    for (int i = 0; i < path.size(); i ++ )
    {
        if (tmp == d[path[i]]) l = i;
        if (i < path.size() - 1) tmp += w[fa[path[i + 1]]];//记录直径上距离不唯一的
    }
    tmp = 0;
    for (int i = path.size() - 1; i >= 0; i -- )
    {
        if (tmp == d[path[i]]) r = i;
        if (i > 0) tmp += w[fa[path[i]]];
    }

    cout << max(0, r - l) << '\n';//答案

    return 0;
}

/*
            整体思路：二分图最小路径覆盖
                      题意就是求一个图中最少多少路径覆盖
                      我们知道二分图最小路径覆盖是等于
                      总点数 - 最大匹配数的
                      所以直接打一个二分图匹配就行了
*/
#include <bits/stdc++.h>

using namespace std;

const int N = 130;

int n, m;
bool g[N][N], st[N];
int match[N];

bool find(int u)
{
    for (int i = 1; i <= n; i ++ )
        if (g[u][i] && !st[i])
        {
            st[i] = true;
            if (!match[i] || find(match[i]))
            {//二分图匹配，匈牙利算法
                match[i] = u;
                return true;
            }
        }

    return false;
}

int main()
{
    int T;
    cin >> T;
    while (T -- )//多组数据
    {
        memset(g, 0, sizeof g);
        memset(match, 0, sizeof match);//初始化
        cin >> n >> m;
        for (int i = 1; i <= m; i ++ )
        {
            int a, b;
            cin >> a >> b;//加边
            g[a][b] = true;
        }

        int res = n;//总点数
        for (int i = 1; i <= n; i ++ )
        {
            memset(st, 0, sizeof st);//匹配
            if (find(i)) res -- ;//减匹配数
        }

        cout << res << '\n';//答案
    }

    return 0;
}

/*
            整体思路：dijkstra求最短路与次短路 + 方案数
                      看到题目可以知道这是一道最短路的题目
                      然后因为边权没有负数，所以可以用dijkstra
                      再加上方案数，套个模板就行了
*/
#include <bits/stdc++.h>

using namespace std;

const int N = 1010, M = 10010;

int n, m;
int h[N], e[M], w[M], ne[M], idx;
int cnt[N][2], f[N][2];
bool st[N][2];
int s, t;
struct Hatsune
{
    int x, id, dis;
    bool operator < (const Hatsune &W) const
    {
        return dis > W.dis;//重载运算符
    }
};

void init()
{
    memset(h, -1, sizeof h);
    idx = 0;
    memset(cnt, 0, sizeof cnt);
    memset(f, 0x3f, sizeof f);
    memset(st, 0, sizeof st);//初始化
}

void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;//加边，带权
}

void dijkstra()
{
    priority_queue<Hatsune> heap;
    heap.push({s, 0, 0});
    f[s][0] = 0;
    cnt[s][0] = 1;//初始第一个点
    while (heap.size())
    {
        auto t = heap.top();
        heap.pop();

        int id = t.id, x = t.x;

        if (st[x][id]) continue;
        st[x][id] = true;

        for (int i = h[x]; ~i; i = ne[i])
        {
            int j = e[i], distance = w[i];

            if (f[j][0] > f[x][id] + distance)
            {
                f[j][1] = f[j][0];
                cnt[j][1] = cnt[j][0];
                heap.push({j, 1, f[j][1]});
                f[j][0] = f[x][id] + distance;//更新最短路、次短路
                cnt[j][0] = cnt[x][id];
                heap.push({j, 0, f[j][0]});
            }
            else if (f[j][0] == f[x][id] + distance) cnt[j][0] += cnt[x][id];//方案
            else if (f[j][1] > f[x][id] + distance)
            {
                f[j][1] = f[x][id] + distance;
                cnt[j][1] = cnt[x][id];
                heap.push({j, 1, f[j][1]});//更新次短路
            }
            else if (f[j][1] == f[x][id] + distance) cnt[j][1] += cnt[x][id];//方案
        }
    }
}

int main()
{
    int T;
    cin >> T;
    while (T -- )//多组数据
    {
        init();
        cin >> n >> m;
        for (int i = 1; i <= m; i ++ )
        {
            int a, b, c;
            cin >> a >> b >> c;
            add(a, b, c);//加边
        }
        cin >> s >> t;

        dijkstra();

       if (f[t][0] == f[t][1] - 1) cout << cnt[t][0] + cnt[t][1] << '\n';//答案
       else cout << cnt[t][0] << '\n';
    }

    return 0;
}

/*
            整体思路：图论最短路 + 节点扩展到二维
                      一眼模板，然后模拟就行了
*/
#include <bits/stdc++.h>

using namespace std;

const int N = 1010;

int n, m, start;
struct Miku
{
    int val, dep, id;
    bool operator < (const Miku &W) const
    {
        return val > W.val;//重载运算符
    }
};
int dist[N][N], g[N];

void dijkstra()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1][start] = 0;
    priority_queue<Miku> heap;
    heap.push({0, 1, start});

    while (heap.size())
    {
        auto t = heap.top();
        heap.pop();

        int depth = t.dep, ID = t.id;

        for (int i = 1; i <= m; i ++ )
        {
            if (depth + g[i] < 1 || depth + g[i] > n) continue;
            if (dist[depth + g[i]][i] > dist[depth][ID] + 2 * abs(g[i]) + abs(i - ID))
            {//按题目条件模拟
                dist[depth + g[i]][i] = dist[depth][ID] + 2 * abs(g[i]) + abs(i - ID);
                heap.push({dist[depth + g[i]][i], depth + g[i], i});
            }
        }
    }
}

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= m; i ++ )
    {
        cin >> g[i];
        if (g[i] == 0) start = i;
    }

    dijkstra();

    int res = 0x3f3f3f3f;
    for (int i = 1; i <= m; i ++ ) res = min(res, dist[n][i]);//求解

    if (res == 0x3f3f3f3f) cout << "-1\n";
    else cout << res << '\n';

    return 0;
}