代码概述：建边边权用相反数， 然后跑DIJ

#include <bits/stdc++.h>
using namespace std;
int n, m;
const int MAXN = 2000;
const int MAXM = 5 * 1e4 + 5;
struct Node{
	int to, next, w;
}e[2 * MAXM];
int head[MAXN];
int cnt;
void init(){
	for(int i = 0; i < MAXN; i++){
		head[i] = -1;
	}
	cnt = 0;
}
void add(int x, int y, int w){
	e[cnt].next = head[x];
	e[cnt].to = y;
	e[cnt].w = w;
	
	head[x] = cnt++;
}
struct Q{
	int i;
	int v;
	friend bool operator <(Q a, Q b){
		return a.v > b.v;
	}
};
bool vis[MAXN];
void dij(){
	priority_queue<Q> q;
	q.push({1, 0});
	while(!q.empty()){
		Q now = q.top();
		q.pop();
		//cout << now.i << ' ' << now.v << endl;
		vis[now.i] = 1;
		if(now.i == n){
			cout << -now.v << endl;
			return;
		}
		for(int i = head[now.i]; ~i; i = e[i].next){
			int v = e[i].to;
			if(vis[v]){
				continue;
			}
			
			q.push({v, now.v + e[i].w});
		}
	}
}
int main(){
	cin >> n >> m;
	init();
	while(m--){
		int x, y, w;
		cin >> x >> y >> w;
		add(x, y, -w);
		//add(y, x, -w);
	}
	dij();
	return 0;
}
/*
4 4
1 2 3
1 3 4
2 4 3
3 4 100

*/