int G[N][N];//二维数组，其初始值即为该图的邻接矩阵

void init()

{

    for (int i = ; i <= n; i++)

    {

        for (int j = ; j <= n; j++)

        {

            G[i][j] = -;//初始化邻接矩阵，用-1代表无穷

        }

        G[i][i] = ;//初始化，自己到自己的路径长度为0

    }

}

void floyd()

{

    for (int k = ; k <= n; k++)//从1至n循环k

    {

        for (int i = ; i <= n; i++)

        {

            for (int j = ; j <= n; j++)//遍历所有的i，j

            {

                if (G[i][k] == -1 || G[k][j] == -1)continue;

                if (G[i][j] == -1 || G[i][k] + G[k][j] < G[i][j])G[i][j] = G[i][k] + G[k][j];

            }

        }

    }

}

#include<cstdio>

const int N = ;

int G[N][N];

int n, m;

void init()

{

    for (int i = ; i <= n; i++)

    {

        for (int j = ; j <= n; j++)

        {

            G[i][j] = -;//初始化为无穷

        }

    }

    for (int i = ; i <= n; i++)G[i][i] = ;//自己到自己距离是0

}

void floyd()

{

    for (int k = ; k <= n; k++)

    {

        for (int i = ; i <= n; i++)

        {

            for (int j = ; j <= n; j++)

            {

                if (G[i][k] == - || G[k][j] == -)continue;

                else if (G[i][j] == - || G[i][j] > G[i][k] + G[k][j])G[i][j] = G[i][k] + G[k][j];

            }

        }

    }

}

int main()

{

    while (scanf("%d%d", &n, &m) != EOF)

    {

        if (n ==  && m == )break;

        init();

        int x, y, t;

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

        {

            scanf("%d%d%d", &x, &y, &t);

            G[x][y] = G[y][x] = t;

        }

        floyd();

        printf("%d\n", G[][n]);

    }

    return ;

}

int G[N][N]; // 图邻接矩阵

int d[N]; // 表示起点到各结点的最短距离

bool vis[N] = { false }; // 表示各结点被访问过与否

void init() // 初始化

{

    for (int i = ; i <= n; i++)

    {

        for (int j = ; j <= n; j++)

        {

            if (i == j) G[i][j] = ;

            else G[i][j] = INF;

        }

    }

}

void Dijkstra(int start)

{

    for (int i = ; i <= n; i++) d[i] = INF;//可达距离都初始化为无穷

    d[start] = ; // 起初只有start结点可达

    for (int i = ; i <= n; i++)

    {

        int u = -; // 距离最近的结点u,初始化为-1

        int min = INF; // min存放最小的d[u]，初始化为无穷

        for (int j = ; j <= n; j++)//得到最近的点

        {

            if (vis[j] == false && d[j] < min)

            {

                u = j; // 与起点直接相连的距离最小结点

                min = d[j];

            }

        }

        if (u == -) return; // 说明剩下的未被访问过的结点都是与起点不可达的

        vis[u] = true; // 设为已读

        for (int v = ; v <= n; v++)//由新得到的点更新后面所有点

        {

            // 此处d[u]有一个相加操作，所以在设置很大整数时不能设置为0x7fffffff，会导致溢出

            if (vis[v] == false && G[u][v] != INF && d[u] + G[u][v] < d[v]) d[v] = d[u] + G[u][v];

        }

    }

}

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

const int N = ;

const int INF = 0x3fffffff;

int n, m;

int G[N][N];

int d[N];//起点到各点的距离

bool vis[N] = { false };

void init()

{

    for (int i = ; i <= n; i++)

    {

        for (int j = ; j <= n; j++)

        {

            G[i][j] = INF;

        }

        G[i][i] = ;

    }

    for (int i = ; i <= n; i++)

    {

        d[i] = INF;

        vis[i] = false;

    }

}

void djkstra(int start)

{

    d[start] = ;

    for (int i = ; i <= n; i++)//每次加入一个结点（这时连起点都还没加入)

    {

        int u = -;//最近的结点

        int min = INF;//最近的距离值

        for (int j = ; j <= n; j++)

        {

            if (vis[j] == false && d[j] < min)

            {

                min = d[j];

                u = j;

            }

        }

        if (u == -)return;//无路可走

        vis[u] = true;

        for (int v = ; v <= n; v++)//更新其他节点

        {

            if (vis[v] == false && G[u][v] != INF && d[v] > d[u] + G[u][v])d[v] = d[u] + G[u][v];

        }

    }

}

int main()

{

    while (scanf("%d%d", &n, &m) != EOF)

    {

        if (n ==  && m == )break;

        init();

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

        {

            int a, b, t;

            scanf("%d%d%d", &a, &b, &t);

            G[a][b] = G[b][a] = t;

        }

        djkstra();

        printf("%d\n", d[n]);

    }

    return ;

}