> #include<stdio.h>
> #include<string.h>
> #define N 5008
> #define INF 0xffff;
> int lowcast[N];
> int num[N];
> unsigned short w[N][N];
> int ans;
> int n,m;
> void input();
> struct node {
>     int u;
>     int v;
>     int value;
> };
> node eg[200005];
> void dikjstra(int start);
> int getsecond();
> void show();
> int main(){
>     //freopen("1.txt","r",stdin);
>     while (scanf("%d%d",&n,&m)!=EOF){
>         input();
>         ans=0;
>         dikjstra(1);
>         for (int i=1;i<=n;i++){
>             num[i]=lowcast[i];
>         }
>         dikjstra(n);
>         ans=getsecond();
>         //show();
>         printf("%d\n",ans);
>     }
> }
> void input(){
>     int a;int b;int c;
>     int s=1;
>     for (int i=1;i<N;i++){
>         for (int j=1;j<N;j++)
>             if (i==j)
>                 w[i][j]=0;
>             else
>             w[i][j]=INF;
>     }
>     for (int i=0;i<m;i++){
>         scanf("%d%d%d",&a,&b,&c);
>         eg[i+1].u=a;
>         eg[i+1].v=b;
>         eg[i+1].value=c;
>         if (c<w[a][b]){
>             w[a][b]=w[b][a]=c;
>         }
>     }
> }
> void dikjstra(int start){
>     memset(lowcast,0,sizeof(lowcast));
>     int used[N]={0};
>     int i,j,k;
>     for (i=1;i<=n;i++){
>         lowcast[i]=w[start][i];
>     }
>     lowcast[start]=0;
>     used[start]=1;
>     for (i=0;i<n;i++){
>         int min=INF;
>         j=1;
>         for (k=1;k<=n;k++){
>             if (min>lowcast[k]&&!used[k]){
>                 min=lowcast[k];
>                 j=k;
>             }
>         }
>         used[j]=1;
>         for (k=1;k<=n;k++){
>             if (lowcast[j]+w[j][k]<lowcast[k]&&!used[k]){
>                 lowcast[k]=lowcast[j]+w[j][k];
>             }
>         }
>     }
> }
> int getsecond(){
>     int i,j,k;
>     int min=INF;
>     int t;
>     for (i=1;i<=m;i++){
>         int tempu=eg[i].u;
>         int tempv=eg[i].v;
>         int tempvalue=eg[i].value;
>         t=lowcast[tempv]+num[tempu]+tempvalue;
>         if (t<min&&t>lowcast[1]){
>             min=t;
>         }
>         t=lowcast[tempu]+num[tempv]+tempvalue;
>         if (t<min&&t>lowcast[1]){
>             min=t;
>         }
>     }
>     return min;
> }
> void show(){
>     for (int i=1;i<=n;i++){
>         for (int j=1;j<=n;j++){
>             printf("%d ",w[i][j]);
>         }
>         printf("\n");
>     }
>     for (int i=1;i<=n;i++){
>         printf("%d ",lowcast[i]);
>     }
>     printf("\n");
>     for (int i=1;i<=n;i++){
>         printf("%d ",num[i]);
>     }
>     printf("\n");
> }