#include<bits/stdc++.h>

#define endl '\n'
#define pii pair<int, int>
#define int long long

using namespace std;

const int N=100010;

int n,m;

struct node{
    int v,e,p;
};

vector<node>g[N],e1[N],e2[N];

int dis[N];

void dijkstra(){
    priority_queue<pii,vector<pii>,greater<pii>>q;
    for(int i=2;i<=n;i++){
        dis[i]=1e18;
    }

    vector<int>vis(n+1,0);

    q.push({0,1});
    while(q.size()){
        auto [distance,u]=q.top();
        q.pop();
        if(vis[u])continue;
        vis[u]=1;
        for(auto [v,e,p]:g[u]){
            if(dis[v]>dis[u]+e){
                dis[v]=dis[u]+e;  
                q.push({dis[v],v});
            }
        }
    }

    for(int i=1;i<=n;i++){
        if(dis[i]==1e18)continue;
        for(auto [v,e,p]:g[i]){
            if(dis[v]==dis[i]+e){
                e1[i].push_back({v,e,p});
            }
        }
    }
}

int dfsn[N],low[N],instk[N],scc[N],cnt,cscc,deg[N];

void tarjan(int u){
    stack<int>stk;
    low[u]=dfsn[u]=++cnt;
    instk[u]=1;
    stk.push(u);//进栈
    for(auto [v,e,p]:e1[u]){
        if(!dfsn[v]){//未访问过
            tarjan(v);//递归
            low[u]=min(low[u],low[v]);
        } else if(instk[v]){//访问过，且q可达p
            low[u]=min(low[u],dfsn[v]);
        }
    }

    if(low[u]==dfsn[u]){// 发现强连通分量的根
        int top;
        cscc++;
        do{
            top=stk.top();
            stk.pop();
            instk[top]=0;
            scc[top]=cscc;// 记录所属的强连通分量
        } while(top!=u);// 直到弹出p才停止
    }
}

void solve(){
    cin>>n>>m;

    cscc=cnt=0;
    for(int i=1;i<=n;i++){
        g[i].clear();
        e1[i].clear();
        e2[i].clear();
        dfsn[i]=instk[i]=deg[i]=low[i]=scc[i]=0;
    }

    for(int i=1;i<=m;i++){
        int u,v,e,p;
        cin>>u>>v>>e>>p;
        g[u].push_back({v,e,p});
    }

    dijkstra();

    for(int i=1;i<=n;i++){
        if(!dfsn[i]){
            tarjan(i);
        }
    }

    for(int u=1;u<=n;u++){
        for(auto [v,e,p]:e1[u]){
            int a=scc[u],b=scc[v];
            if(a!=b){
                deg[b]++;
                e2[a].push_back({b,e,p});
            }
        }
    }

    vector<int>dp(n+1,0);
    queue<int>q;
    q.push(scc[1]);
    while(q.size()){
        auto u=q.front();q.pop();
        for(auto [v,e,p]:e2[u]){
            dp[v]=max(dp[v],dp[u]+p);
            if(--deg[v]==0){
                q.push(v);
            }
        }
    }

    cout<<dis[n]<<' '<<dp[scc[n]]<<endl;
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int t;
    cin>>t;

    while(t--){
        solve();
    }

    
    return 0;
}