贝茜把家搬到了一个小农场，但她常常回到FJ的农场去拜访她的朋友。贝茜很喜欢路边的风景，不想那么快地结束她的旅途，于是她每次回农场，都会选择第二短的路径，而不象我们所习惯的那样，选择最短路。 贝茜所在的乡村有R(1<=R<=100,000)条双向道路，每条路都联结了所有的N(1<=N<=5000)个农场中的某两个。贝茜居住在农场1，她的朋友们居住在农场N（即贝茜每次旅行的目的地）。 贝茜选择的第二短的路径中，可以包含任何一条在最短路中出现的道路，并且，一条路可以重复走多次。当然咯，第二短路的长度必须严格大于最短路（可能有多条）的长度，但它的长度必须不大于所有除最短路外的路径的长度。

* 第1行: 两个整数，N和R，用空格隔开

* 第2..R+1行: 每行包含三个用空格隔开的整数A、B和D，表示存在一条长度为 D(1 <= D <= 5000)的路连接农场A和农场B

* 第1行: 输出一个整数，即从农场1到农场N的第二短路的长度

#include<bits/stdc++.h>

#define setIO(s) freopen(s".in","r",stdin)

#define maxn 1000000

#define inf 0x7f7f7f7f

using namespace std;

int cnt,s;

int hd[maxn],to[maxn],nex[maxn],val[maxn],d[maxn],vis[maxn],f[maxn],g[maxn];

void add(int u,int v,int c){

    nex[++cnt]=hd[u],hd[u]=cnt,to[cnt]=v,val[cnt]=c;

}

struct Edge{

    int u,v,c;

    Edge(int u=0,int v=0,int c=0):u(u),v(v),c(c){}

}edges[maxn];

struct Node{

    int u,dis;

    Node(int u=0,int dis=0):u(u),dis(dis){}

    bool operator<(Node b)const{

        return dis>b.dis;

    }

};

priority_queue<Node>Q;

void dijkstra(){

    memset(vis,0,sizeof(vis));

    for(int i=0;i<maxn;++i) d[i]=inf;

    d[0]=d[s]=0;

    Q.push(Node(s,d[s]));

    while(!Q.empty()){

        Node e=Q.top();Q.pop();

        if(vis[e.u]) continue;

        vis[e.u]=1;

        int u=e.u;

        for(int i=hd[u];i;i=nex[i]){

            if(d[to[i]]>d[u]+val[i]){

                d[to[i]]=d[u]+val[i];

                Q.push(Node(to[i],d[to[i]]));

            }

        }

    }

}

int main(){

    // setIO("input");

    int n,m,tot=0,ans=inf,tmp;

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

    for(int i=1,a,b,c;i<=m;++i) {

        scanf("%d%d%d",&a,&b,&c),add(a,b,c),add(b,a,c);

        edges[++tot]=Edge(a,b,c),edges[++tot]=Edge(b,a,c);

    }

    s=1, dijkstra(),tmp=d[n];

    for(int i=1;i<=n;++i) f[i]=d[i];

    s=n, dijkstra();

    for(int i=1;i<=n;++i) g[i]=d[i];

    for(int i=1;i<=tot;++i) {

        Edge e=edges[i];

        if(f[e.u]+val[i]+g[e.v]<ans&&f[e.u]+val[i]+g[e.v]>tmp)

            ans=f[e.u]+val[i]+g[e.v];

    }

    printf("%d\n",ans);

    return 0;

}