#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include<tuple>
using namespace std;
using namespace __gnu_pbds;
template <typename T>
using ordered_set = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define fastio() ios::sync_with_stdio(false);cin.tie(nullptr);
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define pll pair<ll,ll>
#define pb push_back
#define fi first
#define se second
#define ll long long
#define lld double
#define sz(a) (ll)(a.size())
#define cy cout<<"YES"<<endl
#define cn cout<<"NO"<<endl
#define endl '\n'
const long long LINF = 1e18;
const ll MOD = 1e9+7;
#ifndef ONLINE_JUDGE
#define debug(x) cerr << #x << '=';_print(x);cerr << endl;
#else
#define debug(x)
#endif
void _print(int x) { cerr << x; }
void _print(long long x) { cerr << x; }
void _print(double x) { cerr << x; }
void _print(char x) { cerr << x; }
void _print(const string &x) { cerr << x; }
void _print(bool x) { cerr << (x ? '1' : '0'); }
void _print(pair<ll,ll> p) { cerr << '{' ;_print(p.first);cerr<<' ';_print(p.second);cerr<<'}'; }
template <typename T>
void _print(const vector<T> &v)
{cerr << '[';for (const auto &i : v){_print(i);cerr << ' ';}cerr << ']';}
template <typename T>
void _print(const multiset<T> &s){cerr << '{';for (const auto &i : s){_print(i);cerr << ' ';}cerr << '}';}
template <typename T>
void _print(const set<T> &s){cerr << '{';for (const auto &i : s){_print(i);cerr << ' ';}cerr << '}';}
template <typename K, typename V>
void _print(const map<K, V> &m){cerr << '{'<<endl;for (const auto &p : m){cerr << '(';_print(p.first);cerr << ':';_print(p.second);cerr << ')';}cerr << endl<<'}';}
template <typename T1, typename T2>
void _print(const pair<T1, T2> &p){cerr << '(';_print(p.first);cerr << ',';_print(p.second);cerr << ')';}
ll mod_add(ll&a,ll&b,ll m) {return (a+b)%m;}
ll mod_mul(ll&a,ll&b, ll m) {return (a*b)%m;}
ll mod_sub(ll&a,ll&b,ll m) {return ((a-b)%m+m)%m;}
ll gcd(ll a,ll b) {if(b==0) return a;return gcd(b,a%b);}
ll lcm(ll a,ll b) {return a*b/gcd(a,b);}
ll binExpo(ll a,ll n) {ll res=1;while(n) {if(n&1) {res=(res*a);}a=(a*a); n>>=1;}return res;}
ll N=3*1e5;
ll binExpom(ll a,ll n) {ll res=1;while(n) {if(n&1) {res=(res*a); res%=MOD;}a=(a*a); a%=MOD; n>>=1;}return res;}
ll modInv(ll a,ll mod) {return binExpom(a,mod-2);}
vector<ll>fact(N+2,0);
void calcFact() {fact[0]=1;fact[1]=1;for(ll i=2;i<=N;i++){fact[i]=mod_mul(fact[i-1],i,MOD);}}
ll ncr(ll n,ll r)
{ll numr=fact[n];ll den=mod_mul(fact[n-r],fact[r],MOD);ll ans=(modInv(den,MOD)*numr)%MOD;return ans;}
vector<ll> sieve(ll N) {vector<ll>primes(N+1,1);primes[0]=primes[1]=0;for(int i=2;i*i<=N;i++) {for
(int j=i*i;j<=N;j+=i) {primes[j]=0;}}return primes;}
ll extEuclid(ll a,ll b,ll&x ,ll& y) {
if(b==0) {x=1;y=0;return a;}ll x1,y1;ll d=extEuclid(b,a%b,x1,y1);x=y1;y=x1-y1*(a/b);return d;}
vector<ll> findLps(string &s)
{vector<ll> lps(sz(s) + 1, 0);
ll len = 0;ll i = 1;ll n = sz(s);while (i < n){if (s[i] == s[len]){len++;lps[i] = len;i++;}else{if (len != 0){len = lps[len - 1];}else{len = 0;lps[i] = 0;i++;}}}return lps;}
vector<ll> calcZarray(string &s)
{ll n = sz(s);vector<ll> z(n + 1, 0);ll l = 0;ll r = 0;ll i = 1;while (i < n){
if (i < r){if (z[i - l] < r - l + 1){z[i] = z[i - l];}else{l = i;while (r < n and s[r] == s[r - l])r++;z[i] = r - l;r--;i++;}}else{l = i;r = i;while (r < n and s[r - l] == s[r]){r++;}z[i] = r - l;r--;i++;}}return z;}
vector<ll> segSieve(ll l, ll r, ll n){
vector<ll> prime = sieve(n);vector<ll> rangePrime(n + 1, 1);for (int i = 2; i * i <= r; i++){if (prime[i] == 1){int j = (l / i) * i;if (j < l){j += i;}j = max(i * i, j);for (int init = j - l; init < n; init += i){rangePrime[init] = 0;}}}return rangePrime;}
// /
void rabin_karp(string const& s, string const& t) {
auto f=[&](string str)-> ll{ll ht=0;for(int i=0;i<sz(str);i++) {ht=(ht*31 + str[i]-'a'+1)%MOD;}return ht;};ll h=0;ll n=sz(s);debug(n);vector<ll>ph(n+1,0);for(int i=0;i<n;i++) {ll dig=s[i]-'a'+1;h=(h*31LL+dig)%MOD;ph[i]=h;}ll cnt=0;ll ht=f(t);if(ph[sz(t)-1]==ht) cnt++;ll ws=sz(t);ll sub=binExpo(31,ws);for(int i=1;i<=n-ws;i++) {ll currH=ph[i+ws-1];currH=((currH-ph[i-1]*sub)%MOD + MOD)%MOD;if(currH==ht) cnt++;}}
/*<------------------------------------------------------------------------>*/
void binaryLifting(ll src,ll parent,vector<vector<ll>>&adj,vector<vector<ll>>&dp,vector<ll>&lvl,ll curr) {
lvl[src]=curr;
dp[src][0]=parent;
debug(src)
for(int i=1;i<=19;i++) {
dp[src][i]=dp[dp[src][i-1]][i-1];
}
for(auto nbr:adj[src]) {
if(nbr==parent) continue;
binaryLifting(nbr,src,adj,dp,lvl,curr+1);
}
}
vector<vector<ll>> buildSparseTable(ll n,vector<ll>&a) {
vector<vector<ll>>st(20,vector<ll>(n+2,0));
n=a.size();
for(int i=0;i<n;i++) {
st[0][i]=a[i];
}
for(int i=1;(1<<i)<=n;i++) {
for(int j=0;j+(1<<i)<=n;j++) {
st[i][j]=min(st[i-1][j],st[i-1][j+(1<<(i-1))]);
// st[i][j]=gcd(st[i-1][j],st[i-1][j+(1<<(i-1))]);
}
}
return st;
}
vector<ll> logTable(ll n) {
vector<ll>lg(n+2,0);
lg[1]=0;
for(int i=2;i<=n;i++) {
lg[i]=lg[i/2]+1;
}
return lg;
}
class SegTree {
private:
vector<ll>seg;
ll size;
public:
SegTree(ll n) {
// this->size=n;
seg.resize(4*n+1,0);
}
void build(ll src,ll tl,ll tr,vector<ll>&a) {
if(tl>tr) return;
if(tl==tr) {
seg[src]= a[tl];
// seg[src]=vector<ll>(1,a[tl]);
return;
}
ll tm=tl+(tr-tl)/2;
build(2*src+1,tl,tm,a);
build(2*src+2,tm+1,tr,a);
seg[src]=(seg[2*src+1]+seg[2*src+2]);
// seg[src]=max(seg[2*src+1],seg[2*src+2]);
// merge(all(seg[2*src+1]),all(seg[2*src+2]),seg[src].begin());
}
void update(ll src,ll tl,ll tr,ll& pos,ll &val) {
if(tl>tr) return;
if(tl==tr) {
seg[src]=val;
return;
}
ll tm=tl+(tr-tl)/2;
if(pos<=tm) {
update(2*src+1,tl,tm,pos,val);
}else {
update(2*src+2,tm+1,tr,pos,val);
}
// seg[src]=max(seg[2*src+1],seg[2*src+2]);
seg[src]=(seg[2*src+1]+seg[2*src+2]);
// seg[src]=merge(seg[2*src+1],seg[2*src+2]);
}
ll findmn(ll src,ll tl,ll tr,ll k) {
if(tl==tr) {
return tl;
}
ll ans=1e6;
ll tm=tl+(tr-tl)/2;
if(seg[2*src+1]>=k) {
ans=min(ans,findmn(2*src+1,tl,tm,k));
}
else if(seg[2*src+2]>=k) {
ans=min(ans,findmn(2*src+2,tm+1,tr,k));
}
return ans;
}
ll findSum(ll src,ll tl,ll tr, ll l ,ll r) {
if(l>r) {
return 0;
}
if(tl==l and tr==r) return seg[src];
ll tm=tl+(tr-tl)/2;
return findSum(2*src+1,tl,tm,l,min(tm,r)) + findSum(2*src+2,tm+1,tr,max(tm+1,l),r);
}
};
vector<ll> manacher(string ns){
ll l=0;
ll r=1;
ll n=sz(ns);
vector<ll>d(n,0);
for(int i=1;i<=sz(ns)-2;i++) {
d[i]=min(r-i,d[l+(r-i)]);
while(ns[i-d[i]] == ns[i+d[i]]) d[i]++;
if(i+d[i]>r) {
l=i-d[i];
r=i+d[i];
}
}
return vector<ll>(begin(d)+1,end(d)-1);
}
/*
think of binary search
think in reverese direction
solve equation mathematically
try to merge two operation in one or split one operation in two
find optimal soln without using operation
*/
// d[0]=1;
// derangement d(n)=(n-1)*(d(n-1)+d(n-2));
void solve() {
ll n,m;
cin>>n>>m;
vector<vector<vector<ll>>>adj(n+1);
map<pll,ll>mp;
map<pll,ll>ct;
for(int i=1;i<=m;i++) {
ll u,v,w1,w2;
cin>>u>>v>>w1>>w2;
adj[u].pb({v,w1,w2});
adj[v].pb({u,w1,w2});
mp[{u,v}]=w1;
mp[{v,u}]=w1;
ct[{u,v}]=w2;
ct[{v,u}]=w2;
}
vector<map<ll,ll>>sm(n+1);
for(int u=1;u<=n;u++) {
for(auto v:adj[u]) {
sm[u][v[1]]+=v[2];
}
}
// vector<ll>vis(n+1,0);
// auto dfs=[&](auto&&f,ll src) -> void {
// vis[src]=1;
// for(auto nbr:adj[src]) {
// ll nbrN=nbr[0];
// ll nbrCl=nbr[1];
// ll nbrCc=nbr[2];
// if(vis[nbrN]) {
// sm[src][nbrCl]+=nbrCc;
// continue;
// }
// sm[src][nbrCl]+=nbrCc;
// f(f,nbrN);
// }
// };
// dfs(dfs,1LL);
vector<vector<ll>>d(n+1,vector<ll>(2,LINF));
priority_queue<vector<ll>,vector<vector<ll>>,greater<vector<ll>>>pq;
pq.push({0,1,0,0});
pq.push({0,1,1,0});
d[1][0]=0;
d[1][1]=0;
vector<vector<ll>>vis1(n+1,vector<ll>(2,0));
while(!pq.empty()) {
auto tp=pq.top();
pq.pop();
ll srcN=tp[1];
ll srcD=tp[0];
ll nChng=tp[2];
ll p=tp[3];
if(vis1[srcN][nChng]) continue;
// vis1[srcN][nChng]=1;
for(auto nbr:adj[srcN]) {
ll nbrN=nbr[0];
ll nbrCl=nbr[1];
ll nbrCc=nbr[2];
ll sum=sm[srcN][nbrCl];
if(sum!=nbrCc) {
if(mp[{srcN,p}]==nbrCl) {
ll cs=sum-ct[{srcN,p}];
if(nChng) {
cs-=nbrCc;
if(d[nbrN][0]>srcD+cs) {
d[nbrN][0]=srcD+cs;
pq.push({d[nbrN][0],nbrN,0,srcN});
}
if(d[nbrN][1]>nbrCc+srcD) {
d[nbrN][1]=nbrCc+srcD;
pq.push({d[nbrN][1],nbrN,1,srcN});
}
}else {
// cs+=ct[]
if(d[nbrN][1]>srcD+nbrCc) {
d[nbrN][1]=srcD+nbrCc;
pq.push({d[nbrN][1],nbrN,1,srcN});
}
}
}else {
ll cs=sum-nbrCc;
if(d[nbrN][0]>srcD+cs) {
d[nbrN][0]=srcD+cs;
pq.push({d[nbrN][0],nbrN,0,srcN});
}
if(d[nbrN][1]>srcD+nbrCc) {
d[nbrN][1]=srcD+nbrCc;
pq.push({d[nbrN][1],nbrN,1,srcN});
}
}
}else {
if(d[nbrN][0]>srcD) {
d[nbrN][0]=srcD;
pq.push({d[nbrN][0],nbrN,0,srcN});
}
if(d[nbrN][1]>srcD+nbrCc) {
d[nbrN][1]=srcD+nbrCc;
pq.push({d[nbrN][1],nbrN,1,srcN});
}
}
}
}
// debug(d)
if(min(d[n][0],d[n][1])==LINF) {
cout<<-1<<endl;
return;
}
cout<<min(d[n][0],d[n][1])<<endl;
}
int main()
{
// freopen("shortcut.in", "r", stdin);
// freopen("shortcut.out", "w", stdout);
fastio()
#ifndef ONLINE_JUDGE
freopen("errorf.in","w",stderr);
#endif
ll int t=1;
// cin >> t;
while(t--) solve();
return 0;
}
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include<tuple>
using namespace std;
using namespace __gnu_pbds;
template <typename T>
using ordered_set = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define fastio() ios::sync_with_stdio(false);cin.tie(nullptr);
#define all(v) (v).begin(), (v).end()
#define rall(v) (v).rbegin(), (v).rend()
#define pll pair<ll,ll>
#define pb push_back
#define fi first
#define se second
#define ll long long
#define lld double
#define sz(a) (ll)(a.size())
#define cy cout<<"YES"<<endl
#define cn cout<<"NO"<<endl
#define endl '\n'
const long long LINF = 1e18;
const ll MOD = 1e9+7;
#ifndef ONLINE_JUDGE
#define debug(x) cerr << #x << '=';_print(x);cerr << endl;
#else
#define debug(x)
#endif
void _print(int x) { cerr << x; }
void _print(long long x) { cerr << x; }
void _print(double x) { cerr << x; }
void _print(char x) { cerr << x; }
void _print(const string &x) { cerr << x; }
void _print(bool x) { cerr << (x ? '1' : '0'); }
void _print(pair<ll,ll> p) { cerr << '{' ;_print(p.first);cerr<<' ';_print(p.second);cerr<<'}'; }
template <typename T>
void _print(const vector<T> &v)
{cerr << '[';for (const auto &i : v){_print(i);cerr << ' ';}cerr << ']';}
template <typename T>
void _print(const multiset<T> &s){cerr << '{';for (const auto &i : s){_print(i);cerr << ' ';}cerr << '}';}
template <typename T>
void _print(const set<T> &s){cerr << '{';for (const auto &i : s){_print(i);cerr << ' ';}cerr << '}';}
template <typename K, typename V>
void _print(const map<K, V> &m){cerr << '{'<<endl;for (const auto &p : m){cerr << '(';_print(p.first);cerr << ':';_print(p.second);cerr << ')';}cerr << endl<<'}';}
template <typename T1, typename T2>
void _print(const pair<T1, T2> &p){cerr << '(';_print(p.first);cerr << ',';_print(p.second);cerr << ')';}
ll mod_add(ll&a,ll&b,ll m) {return (a+b)%m;}
ll mod_mul(ll&a,ll&b, ll m) {return (a*b)%m;}
ll mod_sub(ll&a,ll&b,ll m) {return ((a-b)%m+m)%m;}
ll gcd(ll a,ll b) {if(b==0) return a;return gcd(b,a%b);}
ll lcm(ll a,ll b) {return a*b/gcd(a,b);}
ll binExpo(ll a,ll n) {ll res=1;while(n) {if(n&1) {res=(res*a);}a=(a*a); n>>=1;}return res;}
ll N=3*1e5;
ll binExpom(ll a,ll n) {ll res=1;while(n) {if(n&1) {res=(res*a); res%=MOD;}a=(a*a); a%=MOD; n>>=1;}return res;}
ll modInv(ll a,ll mod) {return binExpom(a,mod-2);}
vector<ll>fact(N+2,0);
void calcFact() {fact[0]=1;fact[1]=1;for(ll i=2;i<=N;i++){fact[i]=mod_mul(fact[i-1],i,MOD);}}
ll ncr(ll n,ll r)
{ll numr=fact[n];ll den=mod_mul(fact[n-r],fact[r],MOD);ll ans=(modInv(den,MOD)*numr)%MOD;return ans;}
vector<ll> sieve(ll N) {vector<ll>primes(N+1,1);primes[0]=primes[1]=0;for(int i=2;i*i<=N;i++) {for
(int j=i*i;j<=N;j+=i) {primes[j]=0;}}return primes;}
ll extEuclid(ll a,ll b,ll&x ,ll& y) {
if(b==0) {x=1;y=0;return a;}ll x1,y1;ll d=extEuclid(b,a%b,x1,y1);x=y1;y=x1-y1*(a/b);return d;}
vector<ll> findLps(string &s)
{vector<ll> lps(sz(s) + 1, 0);
ll len = 0;ll i = 1;ll n = sz(s);while (i < n){if (s[i] == s[len]){len++;lps[i] = len;i++;}else{if (len != 0){len = lps[len - 1];}else{len = 0;lps[i] = 0;i++;}}}return lps;}
vector<ll> calcZarray(string &s)
{ll n = sz(s);vector<ll> z(n + 1, 0);ll l = 0;ll r = 0;ll i = 1;while (i < n){
if (i < r){if (z[i - l] < r - l + 1){z[i] = z[i - l];}else{l = i;while (r < n and s[r] == s[r - l])r++;z[i] = r - l;r--;i++;}}else{l = i;r = i;while (r < n and s[r - l] == s[r]){r++;}z[i] = r - l;r--;i++;}}return z;}
vector<ll> segSieve(ll l, ll r, ll n){
vector<ll> prime = sieve(n);vector<ll> rangePrime(n + 1, 1);for (int i = 2; i * i <= r; i++){if (prime[i] == 1){int j = (l / i) * i;if (j < l){j += i;}j = max(i * i, j);for (int init = j - l; init < n; init += i){rangePrime[init] = 0;}}}return rangePrime;}
// /
void rabin_karp(string const& s, string const& t) {
auto f=[&](string str)-> ll{ll ht=0;for(int i=0;i<sz(str);i++) {ht=(ht*31 + str[i]-'a'+1)%MOD;}return ht;};ll h=0;ll n=sz(s);debug(n);vector<ll>ph(n+1,0);for(int i=0;i<n;i++) {ll dig=s[i]-'a'+1;h=(h*31LL+dig)%MOD;ph[i]=h;}ll cnt=0;ll ht=f(t);if(ph[sz(t)-1]==ht) cnt++;ll ws=sz(t);ll sub=binExpo(31,ws);for(int i=1;i<=n-ws;i++) {ll currH=ph[i+ws-1];currH=((currH-ph[i-1]*sub)%MOD + MOD)%MOD;if(currH==ht) cnt++;}}
/*<------------------------------------------------------------------------>*/
void binaryLifting(ll src,ll parent,vector<vector<ll>>&adj,vector<vector<ll>>&dp,vector<ll>&lvl,ll curr) {
lvl[src]=curr;
dp[src][0]=parent;
debug(src)
for(int i=1;i<=19;i++) {
dp[src][i]=dp[dp[src][i-1]][i-1];
}
for(auto nbr:adj[src]) {
if(nbr==parent) continue;
binaryLifting(nbr,src,adj,dp,lvl,curr+1);
}
}
vector<vector<ll>> buildSparseTable(ll n,vector<ll>&a) {
vector<vector<ll>>st(20,vector<ll>(n+2,0));
n=a.size();
for(int i=0;i<n;i++) {
st[0][i]=a[i];
}
for(int i=1;(1<<i)<=n;i++) {
for(int j=0;j+(1<<i)<=n;j++) {
st[i][j]=min(st[i-1][j],st[i-1][j+(1<<(i-1))]);
// st[i][j]=gcd(st[i-1][j],st[i-1][j+(1<<(i-1))]);
}
}
return st;
}
vector<ll> logTable(ll n) {
vector<ll>lg(n+2,0);
lg[1]=0;
for(int i=2;i<=n;i++) {
lg[i]=lg[i/2]+1;
}
return lg;
}
class SegTree {
private:
vector<ll>seg;
ll size;
public:
SegTree(ll n) {
// this->size=n;
seg.resize(4*n+1,0);
}
void build(ll src,ll tl,ll tr,vector<ll>&a) {
if(tl>tr) return;
if(tl==tr) {
seg[src]= a[tl];
// seg[src]=vector<ll>(1,a[tl]);
return;
}
ll tm=tl+(tr-tl)/2;
build(2*src+1,tl,tm,a);
build(2*src+2,tm+1,tr,a);
seg[src]=(seg[2*src+1]+seg[2*src+2]);
// seg[src]=max(seg[2*src+1],seg[2*src+2]);
// merge(all(seg[2*src+1]),all(seg[2*src+2]),seg[src].begin());
}
void update(ll src,ll tl,ll tr,ll& pos,ll &val) {
if(tl>tr) return;
if(tl==tr) {
seg[src]=val;
return;
}
ll tm=tl+(tr-tl)/2;
if(pos<=tm) {
update(2*src+1,tl,tm,pos,val);
}else {
update(2*src+2,tm+1,tr,pos,val);
}
// seg[src]=max(seg[2*src+1],seg[2*src+2]);
seg[src]=(seg[2*src+1]+seg[2*src+2]);
// seg[src]=merge(seg[2*src+1],seg[2*src+2]);
}
ll findmn(ll src,ll tl,ll tr,ll k) {
if(tl==tr) {
return tl;
}
ll ans=1e6;
ll tm=tl+(tr-tl)/2;
if(seg[2*src+1]>=k) {
ans=min(ans,findmn(2*src+1,tl,tm,k));
}
else if(seg[2*src+2]>=k) {
ans=min(ans,findmn(2*src+2,tm+1,tr,k));
}
return ans;
}
ll findSum(ll src,ll tl,ll tr, ll l ,ll r) {
if(l>r) {
return 0;
}
if(tl==l and tr==r) return seg[src];
ll tm=tl+(tr-tl)/2;
return findSum(2*src+1,tl,tm,l,min(tm,r)) + findSum(2*src+2,tm+1,tr,max(tm+1,l),r);
}
};
vector<ll> manacher(string ns){
ll l=0;
ll r=1;
ll n=sz(ns);
vector<ll>d(n,0);
for(int i=1;i<=sz(ns)-2;i++) {
d[i]=min(r-i,d[l+(r-i)]);
while(ns[i-d[i]] == ns[i+d[i]]) d[i]++;
if(i+d[i]>r) {
l=i-d[i];
r=i+d[i];
}
}
return vector<ll>(begin(d)+1,end(d)-1);
}
/*
think of binary search
think in reverese direction
solve equation mathematically
try to merge two operation in one or split one operation in two
find optimal soln without using operation
*/
// d[0]=1;
// derangement d(n)=(n-1)*(d(n-1)+d(n-2));
void solve() {
ll n,m;
cin>>n>>m;
vector<vector<vector<ll>>>adj(n+1);
map<pll,ll>mp;
map<pll,ll>ct;
for(int i=1;i<=m;i++) {
ll u,v,w1,w2;
cin>>u>>v>>w1>>w2;
adj[u].pb({v,w1,w2});
adj[v].pb({u,w1,w2});
mp[{u,v}]=w1;
mp[{v,u}]=w1;
ct[{u,v}]=w2;
ct[{v,u}]=w2;
}
vector<map<ll,ll>>sm(n+1);
for(int u=1;u<=n;u++) {
for(auto v:adj[u]) {
sm[u][v[1]]+=v[2];
}
}
// vector<ll>vis(n+1,0);
// auto dfs=[&](auto&&f,ll src) -> void {
// vis[src]=1;
// for(auto nbr:adj[src]) {
// ll nbrN=nbr[0];
// ll nbrCl=nbr[1];
// ll nbrCc=nbr[2];
// if(vis[nbrN]) {
// sm[src][nbrCl]+=nbrCc;
// continue;
// }
// sm[src][nbrCl]+=nbrCc;
// f(f,nbrN);
// }
// };
// dfs(dfs,1LL);
vector<vector<ll>>d(n+1,vector<ll>(2,LINF));
priority_queue<vector<ll>,vector<vector<ll>>,greater<vector<ll>>>pq;
pq.push({0,1,0,0});
pq.push({0,1,1,0});
d[1][0]=0;
d[1][1]=0;
vector<vector<ll>>vis1(n+1,vector<ll>(2,0));
while(!pq.empty()) {
auto tp=pq.top();
pq.pop();
ll srcN=tp[1];
ll srcD=tp[0];
ll nChng=tp[2];
ll p=tp[3];
if(vis1[srcN][nChng]) continue;
// vis1[srcN][nChng]=1;
for(auto nbr:adj[srcN]) {
ll nbrN=nbr[0];
ll nbrCl=nbr[1];
ll nbrCc=nbr[2];
ll sum=sm[srcN][nbrCl];
if(sum!=nbrCc) {
if(mp[{srcN,p}]==nbrCl) {
ll cs=sum-ct[{srcN,p}];
if(nChng) {
cs-=nbrCc;
if(d[nbrN][0]>srcD+cs) {
d[nbrN][0]=srcD+cs;
pq.push({d[nbrN][0],nbrN,0,srcN});
}
if(d[nbrN][1]>nbrCc+srcD) {
d[nbrN][1]=nbrCc+srcD;
pq.push({d[nbrN][1],nbrN,1,srcN});
}
}else {
// cs+=ct[]
if(d[nbrN][1]>srcD+nbrCc) {
d[nbrN][1]=srcD+nbrCc;
pq.push({d[nbrN][1],nbrN,1,srcN});
}
}
}else {
ll cs=sum-nbrCc;
if(d[nbrN][0]>srcD+cs) {
d[nbrN][0]=srcD+cs;
pq.push({d[nbrN][0],nbrN,0,srcN});
}
if(d[nbrN][1]>srcD+nbrCc) {
d[nbrN][1]=srcD+nbrCc;
pq.push({d[nbrN][1],nbrN,1,srcN});
}
}
}else {
if(d[nbrN][0]>srcD) {
d[nbrN][0]=srcD;
pq.push({d[nbrN][0],nbrN,0,srcN});
}
if(d[nbrN][1]>srcD+nbrCc) {
d[nbrN][1]=srcD+nbrCc;
pq.push({d[nbrN][1],nbrN,1,srcN});
}
}
}
}
// debug(d)
if(min(d[n][0],d[n][1])==LINF) {
cout<<-1<<endl;
return;
}
cout<<min(d[n][0],d[n][1])<<endl;
}
int main()
{
// freopen("shortcut.in", "r", stdin);
// freopen("shortcut.out", "w", stdout);
fastio()
#ifndef ONLINE_JUDGE
freopen("errorf.in","w",stderr);
#endif
ll int t=1;
// cin >> t;
while(t--) solve();
return 0;
}
