#include "bits/stdc++.h" using namespace std; using ll=long long; using dd=double; using vll=vector< ll>; using vdd=vector< dd>; using vvll=vector< vll>; using vvdd=vector; using vvvll=vector< vvll>; using vvvdd=vector; using vvvvll=vector; using pll=pair; using tll=tuple; using qll=tuple; using vpll=vector< pll>; using vtll=vector< tll>; using vqll=vector< qll>; using vvpll=vector; using vvtll=vector; using vvqll=vector; constexpr ll INF = 1LL << 60; struct Fast{ Fast(){ cin.tie(0); ios::sync_with_stdio(false); cout<::max_digits10); } } fast; #define REPS(i, S, E) for (ll i = (S); i <= (E); i++) #define REP(i, N) REPS(i, 0, (N)-1) #define DEPS(i, S, E) for (ll i = (E); i >= (S); i--) #define DEP(i, N) DEPS(i, 0, (N)-1) #define rep(i, S, E) for (ll i = (S); i <= (E); i++) #define dep(i, E, S) for (ll i = (E); i >= (S); i--) #define each(e, v) for (auto&& e : v) #define ALL(v) (v).begin(), (v).end() #define RALL(v) (v).rbegin(), (v).rend() template inline bool chmax(T &a, T b) { if (a < b) { a = b; return true; }return false; } template inline bool chmin(T &a, T b) { if (a > b) { a = b; return true; }return false; } template inline T MaxE(vector&v,ll S,ll E){ T m=v[S]; rep(i,S,E)chmax(m,v[i]); return m; } template inline T MinE(vector&v,ll S,ll E){ T m=v[S]; rep(i,S,E)chmin(m,v[i]); return m; } template inline T MaxE(vector &v) { return MaxE(v,0,(ll)v.size()-1); } template inline T MinE(vector &v) { return MinE(v,0,(ll)v.size()-1); } template inline T Sum(vector &v,ll S,ll E){ T s=T(); rep(i,S,E)s+=v[i]; return s; } template inline T Sum(vector &v) { return Sum(v,0,v.size()-1); } template inline ll sz(T &v){ return (ll)v.size(); } inline ll CEIL(ll a,ll b){ return (a<0) ? -(-a/b) : (a+b-1)/b; } inline ll FLOOR(ll a,ll b){ return -CEIL(-a,b); } //pair用テンプレート using vpll=vector< pll>; using vvpll=vector; template inline pair& operator+=(pair &a,const pair &b){ a.first+=b.first; a.second+=b.second; return a; } template inline pair& operator-=(pair &a,const pair &b){ a.first-=b.first; a.second-=b.second; return a; } template inline pair& operator*=(pair &a,const pair &b){ a.first*=b.first; a.second*=b.second; return a; } template inline pair& operator/=(pair &a,const pair &b){ a.first/=b.first; a.second/=b.second; return a; } template inline pair& operator%=(pair &a,const pair &b){ a.first%=b.first; a.second%=b.second; return a; } template inline pair& operator+=(pair &a,R b){ a.first+=b; a.second+=b; return a; } template inline pair& operator-=(pair &a,R b){ a.first-=b; a.second-=b; return a; } template inline pair& operator*=(pair &a,R b){ a.first*=b; a.second*=b; return a; } template inline pair& operator/=(pair &a,R b){ a.first/=b; a.second/=b; return a; } template inline pair& operator%=(pair &a,R b){ a.first%=b; a.second%=b; return a; } template inline pair operator+(const pair &a,R b){ pair c=a; return c+=b; } template inline pair operator-(const pair &a,R b){ pair c=a; return c-=b; } template inline pair operator*(const pair &a,R b){ pair c=a; return c*=b; } template inline pair operator/(const pair &a,R b){ pair c=a; return c/=b; } template inline pair operator%(const pair &a,R b){ pair c=a; return c%=b; } template inline pair operator-(R b,const pair &a){ pair c=-a; return c+=b; } template inline pair operator-(const pair &a){ pair c=a; return c*=(-1); } template inline ostream &operator<<(ostream &os,const pair &a){ return os << a.first << ' ' << a.second; } //vector用テンプレート template inline vector& operator+=(vector &a,const vector &b){ for (ll i=0; i<(ll)a.size(); i++) a[i]+=b[i]; return a; } template inline vector& operator-=(vector &a,const vector &b){ for (ll i=0; i<(ll)a.size(); i++) a[i]-=b[i]; return a; } template inline vector& operator*=(vector &a,const vector &b){ for (ll i=0; i<(ll)a.size(); i++) a[i]*=b[i]; return a; } template inline vector& operator/=(vector &a,const vector &b){ for (ll i=0; i<(ll)a.size(); i++) a[i]/=b[i]; return a; } template inline vector& operator%=(vector &a,const vector &b){ for (ll i=0; i<(ll)a.size(); i++) a[i]%=b[i]; return a; } template inline vector& operator+=(vector &a,S b){ for (T &e: a) e+=b; return a; } template inline vector& operator-=(vector &a,S b){ for (T &e: a) e-=b; return a; } template inline vector& operator*=(vector &a,S b){ for (T &e: a) e*=b; return a; } template inline vector& operator/=(vector &a,S b){ for (T &e: a) e/=b; return a; } template inline vector& operator%=(vector &a,S b){ for (T &e: a) e%=b; return a; } template inline vector operator+(const vector &a,S b){ vector c=a; return c+=b; } template inline vector operator-(const vector &a,S b){ vector c=a; return c-=b; } template inline vector operator*(const vector &a,S b){ vector c=a; return c*=b; } template inline vector operator/(const vector &a,S b){ vector c=a; return c/=b; } template inline vector operator%(const vector &a,S b){ vector c=a; return c%=b; } template inline vector operator-(S b,const vector &a){ vector c=-a; return c+=b; } template inline vector operator-(const vector &a){ vector c=a; return c*=(-1); } template inline ostream &operator<<(ostream &os,const vector &a){ for (ll i=0; i<(ll)a.size(); i++) os<<(i>0?" ":"")< struct mll_{ ll val; mll_(ll v = 0): val(v % MOD){ if (val < 0) val += MOD; } mll_ operator - () const { return -val; } mll_ operator + (const mll_ &b) const { return val + b.val; } mll_ operator - (const mll_ &b) const { return val - b.val; } mll_ operator * (const mll_ &b) const { return val * b.val; } mll_ operator / (const mll_ &b) const { return mll_(*this) /= b; } mll_ operator + (ll b) const { return *this + mll_(b); } mll_ operator - (ll b) const { return *this - mll_(b); } mll_ operator * (ll b) const { return *this * mll_(b); } friend mll_ operator + (ll a,const mll_ &b) { return b + a; } friend mll_ operator - (ll a,const mll_ &b) { return -b + a; } friend mll_ operator * (ll a,const mll_ &b) { return b * a; } friend mll_ operator / (ll a,const mll_ &b) { return mll_(a)/b; } mll_ &operator += (const mll_ &b) { val=(val+b.val)%MOD; return *this; } mll_ &operator -= (const mll_ &b) { val=(val+MOD-b.val)%MOD; return *this; } mll_ &operator *= (const mll_ &b) { val=(val*b.val)%MOD; return *this; } mll_ &operator /= (const mll_ &b) { ll c=b.val,d=MOD,u=1,v=0; while (d){ ll t = c / d; c -= t * d; swap(c,d); u -= t * v; swap(u,v); } val = val * u % MOD; if (val < 0) val += MOD; return *this; } mll_ &operator += (ll b) { return *this += mll_(b); } mll_ &operator -= (ll b) { return *this -= mll_(b); } mll_ &operator *= (ll b) { return *this *= mll_(b); } mll_ &operator /= (ll b) { return *this /= mll_(b); } bool operator == (const mll_ &b) const { return val == b.val; } bool operator != (const mll_ &b) const { return val != b.val; } bool operator == (ll b) const { return *this == mll_(b); } bool operator != (ll b) const { return *this != mll_(b); } friend bool operator == (ll a,const mll_ &b) { return mll_(a) == b.val; } friend bool operator != (ll a,const mll_ &b) { return mll_(a) != b.val; } friend ostream &operator << (ostream &os,const mll_ &a) { return os << a.val; } friend istream &operator >> (istream &is,mll_ &a) { return is >> a.val; } static mll_ Combination(ll a,ll b){ chmin(b,a-b); if (b<0) return mll_(0); mll_ c = 1; rep(i,0,b-1) c *= a-i; rep(i,0,b-1) c /= i+1; return c; } }; //using mll = mll_<1000000007LL>; using mll = mll_<998244353LL>; using vmll = std::vector; using vvmll = std::vector; using vvvmll = std::vector; using vvvvmll = std::vector; #if 0 #include using namespace atcoder; #endif template void cinWGraph(vector> &to, ll nodeNum,ll edgeNum,bool isDirected){ //無向false、有向true to.resize(nodeNum); rep(i,0,edgeNum-1){ ll v,u; T c; ll d; cin >> v >> u >> c >> d; v--; u--; to[v].emplace_back(u,c,d); if (!isDirected) to[u].emplace_back(v,c,d); } } vll Dijkstra(vector> &to, ll s){ ll N = (ll)to.size(); vll dist(N, INF); priority_queue> Q; Q.push(pll(0, s)); dist[s] = 0; while (!Q.empty()){ ll d; ll v; tie(d, v) = Q.top(); Q.pop(); if (d > dist[v]) continue; each(e, to[v]){ ll u; ll c,d; tie(u, c,d) = e; if (chmin(dist[u], dist[v]+c)) Q.push(pll(dist[u], u)); } } return move(dist); } void solve() { ll n,m; cin >> n >> m; vector> to; cinWGraph(to,n,m,false); vll dist1 = Dijkstra(to, 0); //sからの距離が求まる dist[v]:sからvまでの距離 ll d1=dist1[n-1]; ll v=n-1; while (v!=0){ each(e,to[v]){ ll u; ll c,d; tie(u, c,d) = e; if (dist1[v]-dist1[u] == c){ swap(get<1>(e),get<2>(e)); //u→v bool test=false; each(ee,to[u]){ ll uu,cc,dd; tie(uu,cc,dd) = ee; if (uu!=v)continue; swap(get<1>(ee),get<2>(ee)); test=true; break; } assert(test==true); v=u; break; } } } vll dist2 = Dijkstra(to, n-1); ll d2=dist2[0]; cout << d1+d2 << '\n'; } int main(){ #if 1 solve(); //cin2solve(); //generand(); #else ll t; cin >> t; rep(i, 0, t-1){ solve(); //cin2solve(); } #endif return 0; }