例题链接：https://vjudge.net/contest/341090#problem/A

Dijkstra算法：缺点：图中不存在负权边

记录一下大体思路，便于复习：
1.按照题目输入变量，进行初始化（标记点第一个点是false，第一个点到其它点的距离。。。）
2.Dijkstra
几个注意事项：
（1）初始化时，范围是105。
（2）找距离初始点距离最近的未标记点的时候，是dis数组与minx比较，而不是mp数组与minx进行比较。 dis[j]<minx那里
（3）更换dis数组的值时，判断条件是dis[j]>dis[weizhi]+mp[weizhi][j];
（4）在找到weizhi之后，一定要把weizhi标记了

/*少说话，多做事*/
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <sstream>
#include <map>
#include <set>
#include <queue>
#include <stdlib.h>
typedef long long ll;
using namespace std;

#define MAX 0x3f3f3f3

int mp[105][105];          //两者之间的距离
int dis[105];              //起始点到其它点的最短路程
int vis[105];           //标记一个点是否是旧点
int weizhi;                //对到达的点进行位置标记

int m,n,a,b,c; //m是点的个数，n是边的个数，a,b是一条边的两个点，c是权值

void Dijkstra(int m) //这里m是一共有多少个点，求的是1到另外的点的距离最小值
{
    vis[1]=1;             //将初始点标记
    for (int i=1;i<=m;i++)   //记录一开始初始点到各个点的距离
    {
        dis[i]=mp[1][i];
    }
    for (int i=1;i<=m;i++)
    {
        int minx=MAX;
        for (int j=1;j<=m;j++)
        {
            if( dis[j]<minx && vis[j]==0 )  //只要还有新点便进行更新 （重要） -》 我们找的新点是（所有点中 未被标记 且 距离初始点最近 的点）
            {
                minx=dis[j];
                weizhi=j;
            }
        }
        if(minx==MAX) break; //如果距离初始点的距离都为MAX，也就是没有点可以更新，就break；
        vis[weizhi]=1;
        for (int j=1;j<=m;j++)   //只要一个点经过标记点到初始点的距离可以更新，便更新。
        {
            if(vis[j]==0 && dis[j] > (dis[weizhi])+ mp[weizhi][j])
            {
                dis[j]=mp[weizhi][j] + dis[weizhi];
            }
        }
    }
}

void init()
{
    memset(vis, 0, sizeof(vis));  //初始化（标记函数初始化）
    memset(dis, MAX, sizeof(dis));
    for (int i=1;i<=105;i++)           //将两个点之间的距离都设为最大值（最大就是105，105的大小）
        for (int j=1;j<=105;j++)
            mp[i][j]=MAX;

    for (int i=1;i<=n;i++) //遍历n条边，将两个端点之间的距离更新
    {
        cin >> a >> b >> c;
        mp[a][b]=mp[b][a]=c;
    }
}
int main ()
{

    while (cin >> m >> n)   //m表示点数，n表示边数
    {
        if(m==0&&n==0)break;
        init(); //初始化
        Dijkstra(m);
        cout << dis[m] << endl;
    }
    return 0;
}