#pragma GCC optimize(3)
#pragma GCC target("avx")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#pragma GCC optimize(2)
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<queue>
#define INF 1e18
#define MAXN 300010
using namespace std;
typedef long long ll;
struct edge{
    int v,w,c,nxt;
}e[MAXN<<1];
struct Node{
    int x;
    ll d;
    bool operator < (const Node &rhs) const
    {
        return d>rhs.d;
    }
};
int n,m,t,cnt;
int head[MAXN],deg[MAXN];
ll dis[MAXN],C[MAXN];
priority_queue<Node>Q;
bool used[MAXN];
void add (int u,int v,int w,int c)
{
    e[cnt].v=v;
    e[cnt].w=w;
    e[cnt].c=c;
    e[cnt].nxt=head[u];
    head[u]=cnt++;
}
vector<int>V;
void dfs (int u)
{
    used[u]=1;
    for (int i=head[u];i!=-1;i=e[i].nxt)
        if (e[i].w==0)
        {
            if (t==6)
                if (e[i].v==1)
                {
                    printf ("%d ",i);
                }
            deg[e[i].v]++;
            if (used[e[i].v]) return;
            dfs (e[i].v);
        }
}
bool DFS (int u)
{
    bool flag=0;
    used[u]=1;
    for (int i=head[u];i!=-1;i=e[i].nxt)
        if (e[i].w==0)
        {
            if (e[i].v==1) return 1;
            if (used[e[i].v]) return 0;
            flag|=DFS (e[i].v);
        }
    return flag;
}
queue<int>q;
void dij ()
{
    dis[1]=0,C[1]=0;
    Q.push ((Node){1,dis[1]});
    while (1)
    {
        ll dd=-1;
        while (!Q.empty ())
        {
            int u=Q.top().x;
            if (used[u]) Q.pop ();
            else
            {
                dd=dis[u];
                break;
            }
        }
        if (dd==-1||Q.empty ()) break;
        V.clear ();
        while (!Q.empty())
        {
            int u=Q.top().x;
            if (dis[u]!=dd) break;
            Q.pop ();
            if (used[u]) continue;
            V.push_back (u);
            used[u]=1;
        }
        for (int i=0;i<V.size ();i++)
        {
            dfs (V[i]);
            if (t==6) cout<<V[i]<<" ";
        }
        for (int i=0;i<V.size ();i++)
            if (deg[V[i]]==0) q.push (V[i]);
        while (!q.empty ())
        {
            int u=q.front();
            q.pop ();
            for (int i=head[u];i!=-1;i=e[i].nxt)
                if (e[i].w==0)
                {
                    deg[e[i].v]--;
                    if (dis[e[i].v]>dis[u]+e[i].w||(dis[e[i].v]==dis[u]+e[i].w&&C[e[i].v]<C[u]+e[i].c))
                    {
                        dis[e[i].v]=dis[u]+e[i].w;
                        C[e[i].v]=C[u]+e[i].c;
                    }
                    if (deg[e[i].v]==0) q.push (e[i].v);
                }
                else
                {
                    if (dis[e[i].v]>dis[u]+e[i].w||(dis[e[i].v]==dis[u]+e[i].w&&C[e[i].v]<C[u]+e[i].c))
                    {
                        dis[e[i].v]=dis[u]+e[i].w;
                        C[e[i].v]=C[u]+e[i].c;
                        Q.push (((Node){e[i].v,dis[e[i].v]}));
                    }
                }
        }
    }
}
int main()
{
    scanf ("%d",&t);
    while (t--)
    {
        cnt=0;
        memset (used,0,sizeof (used));
        memset (deg,0,sizeof (deg));
        scanf ("%d%d",&n,&m);
        for (int i=1;i<=n;i++) head[i]=-1;
        for (int i=1;i<=m;i++)
        {
            int u,v,w,c;
            scanf ("%d%d%d%d",&u,&v,&w,&c);
            add (u,v,w,c);
        }
        for (int i=1;i<=n;i++) dis[i]=INF,C[i]=-INF;
        if (t==6)
        {
            if (DFS (1)) printf ("FUck");
        }
        dij ();
        printf ("%lld %lld\n",dis[n],C[n]);
    }
    return 0;
}
/*
2
3 3
1 2 1 1
2 3 1 1
1 3 2 0
3 3
1 2 1 1
2 3 1 1
1 3 1 0
*/