#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
#define mp(Tx, Ty) make_pair(Tx, Ty)
#define For(Ti, Ta, Tb) for(auto Ti = (Ta); Ti <= (Tb); Ti++)
#define Dec(Ti, Ta, Tb) for(auto Ti = (Ta); Ti >= (Tb); Ti--)
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define range(Tx) begin(Tx),end(Tx)
const int N = 3e5 + 5;
int n, m;
int h[N], e[N * 2], ne[N * 2], idx;
long long w[N * 2];
int dep[N];
long long maxn[N];
void add(int a, int b, long long c) {
	e[idx] = b, ne[idx] = h[a], w[idx] = c, h[a] = idx++;
}
bool bfs(long long x) {
	memset(dep, 0, sizeof(dep));
	queue<int> q;
	q.push(1);
	dep[1] = 1;
	maxn[1] = 0;
	while (q.size()) {
		int t = q.front();
		q.pop();
		for (int i = h[t]; ~i; i = ne[i]) {
			int j = e[i];
			if (w[i] * dep[t] > x) continue;
			if (!dep[j]) {
				maxn[j] = max(maxn[t], w[i] * dep[t]);
				dep[j] = dep[t] + 1;
				q.push(j);
			} else if (dep[j] == dep[t] + 1) {
				maxn[j] = min(maxn[j], max(maxn[t], w[i] * dep[t]));
			}
		}
	}
	if (dep[n] == 0) return 0;
	else return 1;
}
int main() {
	cin.tie(nullptr)->sync_with_stdio(false);
	memset(h, -1, sizeof(h));
	cin >> n >> m;
	long long l = 0, r = 0;
	For(i, 1, m) {
		int a, b;
		long long c;
		cin >> a >> b >> c;
		add(a, b, c);
		r = max(r, c);
	}
	r *= max(n, m);
	long long ans = 0;
	while (l <= r) {
		long long mid = l + r >> 1;
		if (bfs(mid)) r = mid - 1, ans = mid;
		else l = mid + 1;
	}
	cout << ans;
	return 0;
}