Lennot

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

#define monta 999999999999LL

int main()
{
	cin.sync_with_stdio(false);
	int n,m;
	cin>>n>>m;
	vector<pair<int,long long>> v[n+100001];
	for(int i=0;i<m;i++){
		int a,b,h;
		cin>>a>>b>>h;
		v[a].push_back(make_pair(b+100000,h));
		v[a+100000].push_back(make_pair(b,0));
	}
	priority_queue<pair<long long,int>> q;
	bool t[n+100001];
	long long e[n+100001];
	for(int i=1;i<=n+100000;i++){t[i]=0;e[i]=monta;}
	e[1]=0;
	q.push(make_pair(0,1));
	while (!q.empty()) {
		long long x = -q.top().first;
		int s = q.top().second;
		q.pop();
		if (t[s]) continue;
		t[s] = 1;
		for (unsigned i = 0; i < v[s].size(); i++) {
			int u = v[s][i].first;
			if (x+v[s][i].second < e[u]) {
				e[u] = x+v[s][i].second;
				q.push(make_pair(-e[u],u));
			}
		}
	}
	cout<<min(e[n],e[n+100000])<<endl;
	return 0;
}

Test 1

Group: 1

Verdict: ACCEPTED

Test 2

Group: 1

Verdict: ACCEPTED

Test 3

Group: 1

Verdict: ACCEPTED

Test 4

Group: 1

Verdict: ACCEPTED

Test 5

Group: 1

Verdict: ACCEPTED

Test 6

Group: 2

Verdict: ACCEPTED

Test 7

Group: 2

Verdict: ACCEPTED

Test 8

Group: 2

Verdict: ACCEPTED

Test 9

Group: 2

Verdict: ACCEPTED

Test 10

Group: 2

Verdict: ACCEPTED

Test 11

Group: 3

Verdict: ACCEPTED

Test 12

Group: 3

Verdict: ACCEPTED

Test 13

Group: 3

Verdict: ACCEPTED

Test 14

Group: 3

Verdict: ACCEPTED

Test 15

Group: 3

Verdict: ACCEPTED

Test 16

Group: 3

Verdict: ACCEPTED

Test 17

Group: 3

Verdict: ACCEPTED