Untitled

#include <bits/stdc++.h>

using namespace std;
using pii = pair<int, int>;


int distX[22];
int distY[22];
vector<pii> GX[22];
vector<pii> GY[22];

void dijstra(int kind){

    priority_queue<pii, vector<pii>, greater<pii>> pq;
    if(kind==1){ // x
        distX[1] = 0;
        pq.push({0,1});
        while(!pq.empty()){
            pii cur = pq.top();
            pq.pop();
            int now = cur.second;
            int cur_dist = cur.first;
            if(distX[now] < cur_dist ) continue;
            for(auto next : GX[now]){
                int next_dist = next.first;
                if(distX[next.second] > distX[now] + next_dist){
                    distX[next.second] = distX[now] + next_dist;
                    pq.push({distX[now] + next_dist,next.second});
                }
            }
        }
        return;
    }
    else{ // y 
        distY[1] = 0;
        pq.push({0,1});
        while(!pq.empty()){
            pii cur = pq.top();
            pq.pop();
            int now = cur.second;
            int cur_dist = cur.first;
            if(distY[now] < cur_dist ) continue;
            for(auto next : GY[now]){
                int next_dist = next.first;
                if(distY[next.second] > distY[now] + next_dist){
                    distY[next.second] = distY[now] + next_dist;
                    pq.push({distY[now] + next_dist,next.second});
                }
            }
        }
        return;
    }
}

int main(void){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int INF = 3000000;
    int t;
    cin >> t;
    int n, m, start, end, x, y;
    int cnt;
    while(t--){
        cin >> n >> m ;
        if(m==0){
            cout << "#" << ++cnt << " " << -1 << '\n';
            continue;
        }
        for(int i = 0;i<=20;i++){
            GX[i].clear();
            GY[i].clear();
        }
        fill(distX, distX+21, INF);
        fill(distY,distY+21, INF);
        for(int i = 0 ;i<m;i++){
            cin >> start >> end >> x >> y;
            GX[start].push_back({x,end});
            GX[end].push_back({x,start});
            GY[start].push_back({y,end});
            GY[end].push_back({y,start});
        }
        dijstra(1);
        dijstra(2);
        if(distX[2] * distY[2] >= INF){
            cout << "#" << ++cnt << " " << -1 << '\n';
        }
        else{
            cout << "#" << ++cnt << " " << distX[2] * distY[2] << '\n';
        }
    }
}