#include<bits/stdc++.h>
#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3)
using namespace std;

#define int long long

#define For(i,j,k) for(int i=j;i<=k;i++)
#define Res(i,j,k) for(int i=j;i>=k;i--)
#define endl '\n'
#define IOS ios::sync_with_stdio(0)
#define pb(i) push_back(i)
#define pf(i) push_front(i)
#define mem(a,b) memset(a,b,sizeof a)
const int M = 1000000 + 5;
int n, m;
int x[M], y[M], W[M];
int cnt, hd[M];
struct Edge {
	int to, nxt, w;
} e[M * 2];
int nt, root, tmp, top, idx;
int dfn[M], low[M], vis[M], bel[M];
int cut[M], st[M], siz[M];

void add (int u, int v, int w) {
	e[++cnt].to = v;
	e[cnt].nxt = hd[u];
	e[cnt].w = w;
	hd[u] = cnt;
}

void tarjan (int u) {
	dfn[u] = low[u] = ++tmp;
	st[++top] = u;
	for (int i = hd[u]; i; i = e[i].nxt) {
		int v = e[i].to;
		if (!dfn[v]) {
			tarjan (v);
			low[u] = min (low[u], low[v]);
		} else if (!bel[v]) low[u] = min (low[u], dfn[v]);
	}
	if (dfn[u] == low[u]) {
		siz[++idx] = 1;
		bel[u] = idx;
		while (st[top] != u) {
			bel[st[top]] = idx;
			siz[idx]++;
			top--;
		}
		top--;
	}
}
struct node {
	int dis, u;
	bool operator>(const node& a)const {
		return dis > a.dis;
	}
};
int dis[M];
priority_queue<node, vector<node>, greater<node> >q;
void Dijkstra(int s) {
	memset(dis, 0x3f3f3f3f, sizeof dis);
	dis[s] = 0;
	q.push({0, s});
	while (!q.empty()) {
		int u = q.top().u;
		q.pop();
		if (vis[u]) continue;
		vis[u] = 1;
		for(int i = hd[u];i;i = e[i].nxt){
			int v = e[i].to,w = e[i].w;
			if (dis[v] > dis[u] + w) {
				dis[v] = dis[u] + w;
				q.push({dis[v], v});
			}
		}
	}
}

signed main () {
	ios::sync_with_stdio(0);
	cin.tie();
	cout.tie();
	cin >> n >> m;
	For(i, 1, m) {
		int u, v, w;
		cin >> u >> v >> w;
		x[i] = u, y[i] = v, W[i] = w;
		add(u, v, w);
	}
	For(i, 1, n) {
		if (!dfn[i]) {
			tarjan(i);
		}
	}
	cnt  = 0;
	mem(hd, 0);
	mem(e, 0);
	For(i,1,m) {
		if (bel[x[i]] != bel[y[i]]) {
			add (bel[x[i]], bel[y[i]], W[i]);
		}
	}
	Dijkstra(bel[1]);
	cout << dis[bel[n]];
	return 0;
}

我在学校OJ上交，TLE了两个点