#include <bits/stdc++.h>
#define endl '\n'
#define PRECISION 0
using namespace std;
using ll = long long;
#define fr first
#define sc second
using pl2 = pair<ll, ll>;

const ll INF = 0x3f3f3f3f3f3f3f3f;

bool chk[100020];
vector<pl2> adj[100020];
ll dis[100020];

void Main(){
	int n, m; n = 100000; m = 299991; //cin >> n >> m;
	for (int i = 0; i < n; i++){ /*cin >> chk[i];*/ chk[i] = (i == n-1 ? 1 : 0); } chk[n-1] = 0;
	for (int v = 3; v <= n-2; v++){
		int w = 0, x = 1; // int v, w, x; cin >> v >> w >> x;
		adj[v].push_back({w, x}); adj[w].push_back({v, x});
	}
	for (int v = 3; v <= n-2; v++){
		int w = 2, x = 100000-v; // int v, w, x; cin >> v >> w >> x;
		adj[v].push_back({w, x}); adj[w].push_back({v, x});
	}
	for (int v = 0; v <= n-1; v++){ if (v == 1){ continue; }
		int w = 1, x = 100000; // int v, w, x; cin >> v >> w >> x;
		adj[v].push_back({w, x}); adj[w].push_back({v, x});
	}
	memset(dis, 0x3f, sizeof(dis)); dis[0] = 0;
	priority_queue< pl2, vector<pl2>, greater<pl2> > pq; pq.push({0, 0});
	while (!pq.empty()){
		int now = pq.top().fr; ll dst = pq.top().sc;
		pq.pop();
		if (dis[now] != dst){ continue; }
		for (pl2 p : adj[now]){
			int nxt = p.fr; ll d = p.sc;
			if (chk[nxt]){ continue; }
			if (dis[nxt] <= dst+d){ continue; }
			pq.push({nxt, dst+d}); dis[nxt] = dst+d;
		}
	}
	if (dis[n-1] == INF){ cout << -1; } else{ cout << dis[n-1]; }
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cout.setf(ios::fixed); cout.precision(PRECISION);
	Main();
}
