#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <algorithm>
#include <iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include <stdio.h>
#include <queue>
#include <string.h>
#include <vector>
#include <map>
#define ME(x , y) memset(x , y , sizeof(x))
#define SF(n) scanf("%d" , &n)
#define rep(i , n) for(int i = 0 ; i < n ; i ++)
#define INF  0x3f3f3f3f
#define mod 1024
using namespace std;
typedef long long ll ;
int ma[109][109] ;
int n , m ;

void floyd()
{
    for(int k = 1 ; k <= n ; k++)//通过k定点松弛
    {
        for(int i = 1 ; i <= n ; i++)
        {
            for(int j = 1 ; j <= n ; j++)
            {
                ma[i][j] = min(ma[i][j] , ma[i][k] + ma[k][j]);
            }
        }
    }
}


int main()
{

    while(~scanf("%d%d" , &n , &m) && (m || n))
    {
        memset(ma , INF , sizeof(ma));
        for(int i = 1 ; i <= m ; i++)
        {
            int u , v , w ;
            scanf("%d%d%d" , &u, &v, &w);
            ma[u][v] = ma[v][u] = min(w , ma[u][v]);
        }
        floyd();
        printf("%d\n" , ma[1][n]);
    }

    return 0 ;
}

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <algorithm>
#include <iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include <stdio.h>
#include <queue>
#include <string.h>
#include <vector>
#include <map>
#define ME(x , y) memset(x , y , sizeof(x))
#define SF(n) scanf("%d" , &n)
#define rep(i , n) for(int i = 0 ; i < n ; i ++)
#define INF  0x3f3f3f3f
#define mod 1024
using namespace std;
typedef long long ll ;
int ma[109][109] ;
int n , m ;
int dis[109];
int vis[109];

void Dijkstra()//主要求有源点到各点的最短距离
{
    for(int i = 1 ; i <= n ; i++)
    {
        vis[i] = 0 ;
        dis[i] = ma[1][i];
    }
    vis[1] = 0 ;//有源点
    for(int i = 1 ; i < n ; i++)
    {
        int min1 = INF ;
        int pos ;
        for(int j = 1 ; j <= n ; j++)
        {
            if(!vis[j] && dis[j] < min1)
            {
                min1 = dis[j];
                pos = j ;
            }
        }
        vis[pos] = 1 ;//加入u集合
        for(int j = 1 ; j <= n ; j++)//通过新加入的点，更新u集合到v集合的距离
        {
            dis[j] = min(dis[j] , dis[pos] + ma[pos][j]);//松弛，与prim算法不同的是这里
        }
    }
}


int main()
{

    while(~scanf("%d%d" , &n , &m) && (m || n))
    {
        memset(ma , INF , sizeof(ma));
        for(int i = 1 ; i <= m ; i++)
        {
            int u , v , w ;
            scanf("%d%d%d" , &u, &v, &w);
            ma[u][v] = ma[v][u] = min(w , ma[u][v]);//邻接表建图
        }
        Dijkstra();
        printf("%d\n" , dis[n]);
    }

    return 0 ;
}