Description：

Solution：

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<queue>

#include<vector>

#include<cstring>

using namespace std;

inline int read()

{

    register int res = 0;

    register char c = getchar();

    while(!isdigit(c))c = getchar();

    while(isdigit(c))

    {

        res = (res << 1) + (res << 3) + c - '0';

        c = getchar();

    }

    return res;

}

int n,m;

#define MAXN 250000

struct edge

{

    int to,nxt,v;

}e[MAXN << 1];

int edgenum = 0;

int lin[MAXN] = {0};

void add(int a,int b,int c)

{

    e[edgenum].to = b;e[edgenum].v = c;e[edgenum].nxt = lin[a];lin[a] = edgenum;++edgenum;

    e[edgenum].to = a;e[edgenum].v = c;e[edgenum].nxt = lin[b];lin[b] = edgenum;++edgenum;

    return;

}

int d[MAXN],pre[MAXN];

bool v[MAXN];

int SPFA()

{

    queue<int> q;

    memset(d,0x3f,sizeof(d));

    memset(v,false,sizeof(v));

    q.push(1);d[1] = 0;

    while(!q.empty())

    {

        int k = q.front();q.pop();

        v[k] = false;

        for(int i = lin[k];i != -1;i = e[i].nxt)

        {

            if(d[e[i].to] > d[k] + e[i].v)

            {

                d[e[i].to] = d[k] + e[i].v;

                pre[e[i].to] = i;

                if(!v[e[i].to])

                {

                    v[e[i].to] = true;

                    q.push(e[i].to);

                }

            }

        }

    }

    return d[n];

}

vector<int> g;

int main()

{

    memset(lin,-1,sizeof(lin));

    scanf("%d%d",&n,&m);

    int a,b,c;

    for(int i = 1;i <= m;++i)

    {

        a = read();b = read();c = read();

        add(a,b,c);

    }

    int len = SPFA();

    int ans = 0;

    for(int i = n;i != 1;i = e[pre[i] ^ 1].to)

    {

        g.push_back(pre[i]);

    }

    for(int i = 0;i < g.size();++i)

    {

        int l = e[g[i]].v;

        e[g[i]].v = e[g[i] ^ 1].v = 2 * l;

        ans = max(ans,SPFA());

        e[g[i]].v = e[g[i] ^ 1].v = l;

    }

    cout << ans - len << endl;

    return 0;

}