Lennot

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

using namespace std;
typedef long long ll;
#define F first
#define S second

const int N = 100005;

int n, m;
vector<pair<int, ll>> g[2*N];
ll dist[2*N];
bool vis[2*N];

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> m;
	for (int i = 0; i < m; ++i) {
		int a, b;
		ll h;
		cin >> a >> b >> h;
		g[a].push_back({b+N, h});
		g[a+N].push_back({b, 0});
	}
	for (int i = 0; i < 2*N; ++i) dist[i] = 1000000000000000005;

	priority_queue<pair<ll, int>> q;
	q.push({0, 1});
	dist[1] = 0;
	while (!q.empty()) {
		auto cur = q.top();
		q.pop();
		int cn = cur.S;
		if (vis[cn]) continue;
		vis[cn] = true;
		for (auto a : g[cn]) {
			ll nd = dist[cn]+a.S;
			if (nd < dist[a.F]) {
				dist[a.F] = nd;
				q.push({-nd, a.F});
			}
		}
	}
	cout << min(dist[n], dist[n+N]) << "\n";
	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