#pragma GCC optimize("Ofast,unroll-loops")
#include "train.h"
#include <bits/stdc++.h>
//#define int long long
#define ll long long
#define down cout<<'\n';
#define debug cout<<" cucuucucuuu",down
#define modwwe int t;cin>>t; while(t--)
#define bit(i,j) (i>>j&1)
#define sobit(a) __builtin_popcountll(a)
#define task2 "facttree"
#define task "test"
#define fin(x) freopen(x".inp","r",stdin)
#define fou(x) freopen(x".out","w",stdout)
#define pb push_back
#define mask(k) (1ll<<k)
#define checktime cerr << (double)clock() / CLOCKS_PER_SEC * 1000 << " ms";
using namespace std;
#define getchar_unlocked getchar
mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
int rand(int l, int r) {
return uniform_int_distribution<int>(l, r)(rd);
}
void phongbeo();
const ll inf = 1e17;
const int mod2 = 998244353;
//const ll base=67;
ll n, m, s1, s2, s4, s3, sf, k, s5, s6, s7, s8, s9, mx2, res, dem2 = 0, dem = 0, s33, dem3, dem4, mid, l2,
r2, center;
int i, s10, s12, k1, k2, k3, s11, lim, w, l, r, dem5, dem6, dem7, dem9, root, en;
int el = 19;
struct ib {
ll a, b;
};
vector<ll> dp[100007], dp2[100007], vc[100007], gl, gr, vx[100007], vd[100007];
vector<ib> dc, hihi;
int base = 0;
struct id {
ll l, r;
};
struct ic {
ll a, b, c;
};
vector<vector<ic>>v[100007];
int f[100007], t[100007];
bool cmp(ib x, ib y) {
return x.a < y.a;
}
bool cmk(ib x, ib y) {
return x.b < y.b;
}
struct perseg {
ll t[6000001];
id cur[6000001];
int upd(int u, int l, int r, int x) {
int v = ++dem;
if (l == r) {
t[v] = t[u] + 1;
return v;
}
int mid = l + r >> 1;
cur[v] = cur[u];
if (x <= mid)
cur[v].l = upd(cur[u].l, l, mid, x);
else
cur[v].r = upd(cur[u].r, mid + 1, r, x);
t[v] = t[cur[v].l] + t[cur[v].r];
return v;
}
ll get(int u, int l, int r, int l1, int r1) {
if (l > r1 || r < l1)
return 0;
if (l >= l1 && r <= r1)
return t[u];
int mid = l + r >> 1;
return get(cur[u].l, l, mid, l1, r1) + get(cur[u].r, mid + 1, r, l1, r1);
}
int walk(int u, int v, int l, int r, ll x, ll y, ll ggg) {
if (l == r)
return l;
int mid = l + r >> 1;
if (t[cur[u].l]*ggg + x >= t[cur[v].l]*ggg + y)
return walk(cur[u].l, cur[v].l, l, mid, x, y, ggg);
return walk(cur[u].r, cur[v].r, mid + 1, r, x + t[cur[u].l] * ggg, y + t[cur[v].l] * ggg, ggg);
}
} st;
ll cost(int x, int y, int z) {
return dp2[x][y] + st.get(f[upper_bound(gl.begin(), gl.end(), vc[x][y]) - gl.begin()], -1, gr.size(), 1,
lower_bound(gr.begin(), gr.end(), vc[x][z]) - gr.begin()) * t[x];
}
void huff(int x, int y) {
if (vd[x].size() == 0)
return;
int kk = lower_bound(gr.begin(), gr.end(), vc[x][y]) - gr.begin();
int hihi = upper_bound(vd[x].begin(), vd[x].end(), kk) - vd[x].begin() - 1;
int ff = vx[x][hihi];
dp[x][y] = min(dp[x][y], cost(x, ff, y));
}
int fx(int x, int y, int z) {
int k1 = upper_bound(gl.begin(), gl.end(), vc[x][y]) - gl.begin();
int k2 = upper_bound(gl.begin(), gl.end(), vc[x][z]) - gl.begin();
if (dp2[x][y] + st.t[f[k1]]*t[x] < dp2[x][z] + st.t[f[k2]]*t[x])
return -2;
return st.walk(f[k1], f[k2], -1, gr.size(), dp2[x][y], dp2[x][z], t[x]);
}
void buff(int x, int y) {
int nxt = 0;
while (true) {
if (vx[x].size() == 0)
break;
int hihi = vx[x].back();
int gf = fx(x, hihi, y);
nxt = gf;
if (gf >= vd[x].back() || nxt == -2)
break;
vx[x].pop_back();
vd[x].pop_back();
}
if (nxt != -2) {
if (vx[x].size() == 0)
nxt = 0;
vx[x].pb(y);
vd[x].pb(nxt);
}
}
ll solve(int N, int M, int K, vector<int> T, vector<int> X, vector<int> Y, vector<int> a, vector<int> b,
vector<int> c, vector<int> fl, vector<int> fr) {
n = N;
m = M;
k = K;
for (int i = 1; i <= n; i++)
t[i] = T[i - 1];
dc.pb({1, -1});
vc[1].pb({-1});
vc[n].pb({inf});
dc.pb({n, inf});
/*
for(int i=1; i<=m; i++)
cin>>X[i];
for(int i=1; i<=m; i++)
cin>>Y[i];
for(int i=1; i<=m; i++)
cin>>a[i];
for(int i=1; i<=m; i++)
cin>>b[i];
for(int i=1; i<=m; i++)
cin>>c[i];*/
for (int i = 0; i < m; i++) {
//cin>>X[i]>>Y[i]>>a[i]>>b[i]>>c[i];
X[i]++;
Y[i]++;
vc[X[i]].pb(a[i]);
vc[Y[i]].pb(b[i]);
dc.pb({X[i], a[i]});
dc.pb({Y[i], b[i]});
}/*
for(int i=1; i<=k; i++)
cin>>fl[i];
for(int i=1; i<=k; i++)
cin>>fr[i];*/
gl.pb(inf + 1);
gr.pb(inf + 1);
hihi.pb({inf + 1, inf + 1});
for (int i = 1; i <= k; i++) {
l = fl[i - 1];
r = fr[i - 1];
gl.pb(l);
gr.pb(r);
hihi.pb({l, r});
}
sort(hihi.begin(), hihi.end(), cmp);
sort(gl.begin(), gl.end());
sort(gr.begin(), gr.end());
gr.erase(unique(gr.begin(), gr.end()), gr.end());
for (int i = gl.size() - 1; i >= 0; --i) {
base = st.upd(base, -1, gr.size(), lower_bound(gr.begin(), gr.end(), hihi[i].b) - gr.begin() + 1);
f[i] = base;
}
for (int i = 1; i <= n; i++) {
if (vc[i].size()) {
sort(vc[i].begin(), vc[i].end());
vc[i].erase(unique(vc[i].begin(), vc[i].end()), vc[i].end());
v[i].resize(vc[i].size());
dp[i].resize(vc[i].size());
dp2[i].resize(vc[i].size());
for (int j = 0; j < dp[i].size(); j++)
dp[i][j] = dp2[i][j] = inf;
}
}
for (int i = 0; i < m; i++) {
v[X[i]][lower_bound(vc[X[i]].begin(), vc[X[i]].end(), a[i]) - vc[X[i]].begin()]
.pb({Y[i], lower_bound(vc[Y[i]].begin(), vc[Y[i]].end(), b[i]) - vc[Y[i]].begin(), c[i]});
}
sort(dc.begin(), dc.end(), cmk);
dp2[1][0] = 0;
dp[1][0] = 0;
for (auto x : dc) {
x.b = lower_bound(vc[x.a].begin(), vc[x.a].end(), x.b) - vc[x.a].begin();
huff(x.a, x.b);
buff(x.a, x.b);
for (auto y : v[x.a][x.b]) {
dp2[y.a][y.b] = min(dp2[y.a][y.b], min(dp2[x.a][x.b], dp[x.a][x.b]) + y.c);
dp[y.a][y.b] = min(dp[y.a][y.b], dp2[y.a][y.b]);
}
}
if (min(dp2[n].back(), dp[n].back()) == inf)
return -1;
else
return min(dp2[n].back(), dp[n].back());
}
