#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();
}
I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CiNkZWZpbmUgZW5kbCAnXG4nCiNkZWZpbmUgUFJFQ0lTSU9OIDAKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKdXNpbmcgbGwgPSBsb25nIGxvbmc7CiNkZWZpbmUgZnIgZmlyc3QKI2RlZmluZSBzYyBzZWNvbmQKdXNpbmcgcGwyID0gcGFpcjxsbCwgbGw+OwoKY29uc3QgbGwgSU5GID0gMHgzZjNmM2YzZjNmM2YzZjNmOwoKYm9vbCBjaGtbMTAwMDIwXTsKdmVjdG9yPHBsMj4gYWRqWzEwMDAyMF07CmxsIGRpc1sxMDAwMjBdOwoKdm9pZCBNYWluKCl7CglpbnQgbiwgbTsgbiA9IDEwMDAwMDsgbSA9IDI5OTk5MTsgLy9jaW4gPj4gbiA+PiBtOwoJZm9yIChpbnQgaSA9IDA7IGkgPCBuOyBpKyspeyAvKmNpbiA+PiBjaGtbaV07Ki8gY2hrW2ldID0gKGkgPT0gbi0xID8gMSA6IDApOyB9IGNoa1tuLTFdID0gMDsKCWZvciAoaW50IHYgPSAzOyB2IDw9IG4tMjsgdisrKXsKCQlpbnQgdyA9IDAsIHggPSAxOyAvLyBpbnQgdiwgdywgeDsgY2luID4+IHYgPj4gdyA+PiB4OwoJCWFkalt2XS5wdXNoX2JhY2soe3csIHh9KTsgYWRqW3ddLnB1c2hfYmFjayh7diwgeH0pOwoJfQoJZm9yIChpbnQgdiA9IDM7IHYgPD0gbi0yOyB2KyspewoJCWludCB3ID0gMiwgeCA9IDEwMDAwMC12OyAvLyBpbnQgdiwgdywgeDsgY2luID4+IHYgPj4gdyA+PiB4OwoJCWFkalt2XS5wdXNoX2JhY2soe3csIHh9KTsgYWRqW3ddLnB1c2hfYmFjayh7diwgeH0pOwoJfQoJZm9yIChpbnQgdiA9IDA7IHYgPD0gbi0xOyB2KyspeyBpZiAodiA9PSAxKXsgY29udGludWU7IH0KCQlpbnQgdyA9IDEsIHggPSAxMDAwMDA7IC8vIGludCB2LCB3LCB4OyBjaW4gPj4gdiA+PiB3ID4+IHg7CgkJYWRqW3ZdLnB1c2hfYmFjayh7dywgeH0pOyBhZGpbd10ucHVzaF9iYWNrKHt2LCB4fSk7Cgl9CgltZW1zZXQoZGlzLCAweDNmLCBzaXplb2YoZGlzKSk7IGRpc1swXSA9IDA7Cglwcmlvcml0eV9xdWV1ZTwgcGwyLCB2ZWN0b3I8cGwyPiwgZ3JlYXRlcjxwbDI+ID4gcHE7IHBxLnB1c2goezAsIDB9KTsKCXdoaWxlICghcHEuZW1wdHkoKSl7CgkJaW50IG5vdyA9IHBxLnRvcCgpLmZyOyBsbCBkc3QgPSBwcS50b3AoKS5zYzsKCQlwcS5wb3AoKTsKCQlpZiAoZGlzW25vd10gIT0gZHN0KXsgY29udGludWU7IH0KCQlmb3IgKHBsMiBwIDogYWRqW25vd10pewoJCQlpbnQgbnh0ID0gcC5mcjsgbGwgZCA9IHAuc2M7CgkJCWlmIChjaGtbbnh0XSl7IGNvbnRpbnVlOyB9CgkJCWlmIChkaXNbbnh0XSA8PSBkc3QrZCl7IGNvbnRpbnVlOyB9CgkJCXBxLnB1c2goe254dCwgZHN0K2R9KTsgZGlzW254dF0gPSBkc3QrZDsKCQl9Cgl9CglpZiAoZGlzW24tMV0gPT0gSU5GKXsgY291dCA8PCAtMTsgfSBlbHNleyBjb3V0IDw8IGRpc1tuLTFdOyB9Cn0KCmludCBtYWluKCl7Cglpb3NfYmFzZTo6c3luY193aXRoX3N0ZGlvKDApOyBjaW4udGllKDApOyBjb3V0LnRpZSgwKTsKCWNvdXQuc2V0Zihpb3M6OmZpeGVkKTsgY291dC5wcmVjaXNpb24oUFJFQ0lTSU9OKTsKCU1haW4oKTsKfQo=