#include <bits/stdc++.h>
#define ll long long
#define endl "\n"
using namespace std;
ll n, m, u[5005], v[5005], w[5005], f[105], ans;
bool vis[105];
struct Node
{
    ll v, w;
};
struct cmp
{
    bool operator() (int x, int y)
    {
        return f[x] > f[y];
    }
};
vector <Node> a[105];
ll dij(int s, int t)
{
    priority_queue <int, vector <int>, cmp> q;
    memset(f, 0x3f, sizeof(f));
    memset(vis, 0, sizeof(vis));
    q.push(s);
    f[s] = 0;
    while (! q.empty())
    {
        int x = q.top();
        q.pop();
        for (int i = 0; i < a[x].size(); i++)
        {
            if (!vis[a[x][i].v] && f[a[x][i].v] > f[x] + a[x][i].w)
            {
                f[a[x][i].v] = f[x] + a[x][i].w;
                q.push(a[x][i].v);
            }
        }
        vis[x] = 1;
    }
    return f[t];
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        cin >> u[i] >> v[i] >> w[i];
    }
    for (int i = 1; i <= m; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            a[j].clear();
        }
        w[i] *= 2;
        for (int j = 1; j <= m; j++)
        {
            a[u[j]].push_back({v[j], w[j]});
            a[v[j]].push_back({u[j], w[j]});
        }
        ans = max(ans, dij(1, n));
        w[i] /= 2;
    }
    for (int j = 1; j <= n; j++)
    {
        a[j].clear();
    }
    for (int j = 1; j <= m; j++)
    {
        a[u[j]].push_back({v[j], w[j]});
        a[v[j]].push_back({u[j], w[j]});
    }
    cout << ans - dij(1, n);
    return 0;
}

评测记录