MIKU酱是个玩游戏氪金的人，游戏公司给她制定了新的规则，如果想从关卡i到关卡j，你需要交一些钱就可以了，但同时，MIKU酱的爸爸zjw很爱她，所以她可以每过一关就向她爸要一次钱，但她爸每次给他的钱是固定的，MIKU酱是个不会节省的女孩，哪怕每次多出来的钱，她也会拿去买肥宅快乐水，所以每次要的钱一定花完，因为MIKU酱不想挨骂，所以希望每次他爸给她的钱最少。
tips（到达第n关即通过，每到达一关一定能通过这关）
输入描述:
多组输入，每个样例第一行输入两个整数n,m(2<=n<=200,1<=m<=1000)表示关卡和规则的数量，接下来m行规则，每行输入x,y,w（w<=1000）,表示从关卡x到y需要缴纳w的费用，保证题目有解，不会出现x=y的情况
输出描述:
输出一行，代表最少的钱
示例1
输入
4 4
1 2 2
1 3 1
2 4 3
3 4 1
输出
1
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <cmath>
#include <cstdlib>
#include <ctime>
using namespace std;
#define ll long long
#define P pair<int,int>
#define ph push_back
const int inf=0x3f3f3f3f;
int n,m,x,y,w;
const int N =;
int dis[N];
vector<P>ve[N];
void init(){
for(int i=;i<N;i++) {
dis[i]=inf;
ve[i].clear();
}
}
int bfs(int sta){
priority_queue<P,vector<P>,greater<P> >q;
dis[sta] =;
q.push(P(,sta));
while(!q.empty()){
P p =q.top();
q.pop();
int fi =p.first,se=p.second;//fi：最短路径上到se位置的题目答案
if(se==n) return fi;
for(int i=;i<ve[se].size();i++){
P pp=ve[se][i];
int ff=pp.first,ss=pp.second;
if(dis[ff]>max(ss,fi)){
dis[ff]=max(ss,fi);//变小了
q.push(P(dis[ff],ff));
}
}
}
return inf;
}
int main()
{
while(~scanf("%d%d",&n,&m)){
init();
for(int i=;i<m;i++){
scanf("%d%d%d",&x,&y,&w);
ve[x].ph(P(y,w));
}
int xx = bfs();
printf("%d\n",xx);
}
return ;
}