#include <bits/stdc++.h>
# define endl            '\n'
# define clr(x,a)        memset(x,a,sizeof(x))
# define PI              3.14159265358979323846
# define vi              vector<int>
# define fo(i,n)         for(int i=1;i<=n;i++)
# define all(a)          a.begin(), a.end()
# define deb(x)          cout<<#x<<"=="<<x<<endl;
# define pb              push_back
# define sc              scanf
# define pr              printf
# define tc              int t; cin>>t; while(t--)
# define rev(s)          reverse(s.begin(),s.end())
# define linija          cout<<"____________\n";

using namespace std;
typedef long long ll;

const int mxN=100005, mod=1e9+7;
int n, m, a, b, u, v;
struct slog{
   int node, a, b;
}pom;
vector <slog> graf[mxN];
ll niz[mxN], sol, niz2[mxN];
int vis[mxN];
void dikstra_bajs(){
   queue <int> q;
//   vis[n]=1;
   niz[n]=0;
   q.push(n);
   int node;
   while(q.size()){
      node=q.front();
      q.pop();
//      cout<<"node=="<<node<<" najkraci do njega"<<niz[node]<<endl;
      for(int i=0; i<graf[node].size(); i++){
         if(niz[graf[node][i].node]>niz[node]+graf[node][i].b){
            q.push(graf[node][i].node);
            niz[ graf[node][i].node ]=niz[node]+graf[node][i].b;
         }
//         if(vis[graf[node][i].node]!=1){
//            q.push(graf[node][i].node);
//            vis[ graf[node][i].node ]=1;
//         }
      }
   }
}
void dikstra_auto(){
   queue <int> q;
   q.push(1);
   niz2[1]=0;
   vis[1]=2;
   int node;
   while(q.size()){
      node=q.front();
      q.pop();
//      cout<<"node=="<<node<<" najkraci do njega"<<niz[node]<<endl;
      for(int i=0; i<graf[node].size(); i++){
         if(niz2[graf[node][i].node]>niz2[node]+graf[node][i].a){
            q.push(graf[node][i].node);
            niz2[ graf[node][i].node ]=niz2[node]+graf[node][i].a;
         }
//         if(vis[graf[node][i].node]!=1){
//            q.push(graf[node][i].node);
//            vis[ graf[node][i].node ]=1;
//         }
      }
   }
}

int main(){
   freopen("hurry.in", "r", stdin);
   freopen("hurry.out", "w", stdout);
   tc{
      sc("%d %d", &n, &m);
      for(int i=1; i<=n; i++){
         niz[i]=1e15;
         niz2[i]=1e15;
         graf[i].clear();
         vis[i]=0;
      }
      for(int i=1; i<=m; i++){
         sc("%d %d %d %d", &u, &v, &a, &b);
         pom.a=a;
         pom.b=b;

         pom.node=u;
         graf[v].pb(pom);
         pom.node=v;
         graf[u].pb(pom);
      }
      sol=1e15;
      dikstra_bajs();
      dikstra_auto();
      for(int i=1; i<=n; i++) sol=min(sol, niz2[i]+niz[i]);
      pr("%lld\n", sol);
//      for(int i=1; i<=n; i++) cout<<niz[i]<<" ";
//      cout<<endl;
//      for(int i=1; i<=n; i++) cout<<niz2[i]<<" ";
//      cout<<endl;
//      cout<<endl;
   }

	return 0;
}