#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<queue>
#define INF 1e18
#define MAXN 300010
using namespace std;
#define int long long
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,bool flag)
{
    used[u]=1;
    for (int i=head[u];i!=-1;i=e[i].nxt)
        if (e[i].w==0)
        {
            if (!(flag&(e[i].c==0))) deg[e[i].v]++;
            if (used[e[i].v]) return;
            dfs (e[i].v,flag&(e[i].c==0));
        }
}
bool DFS (int u,bool fl)
{
    used[u]=1;
    bool flag=0;
    for (int i=head[u];i!=-1;i=e[i].nxt)
        if (e[i].w==0)
        {
            if (e[i].v==1)
            {
                printf ("ahah: %d",fl&(e[i].c==0));
                return 1;
            }
            if (used[e[i].v]) return 0;
            if (DFS (e[i].v,fl&(e[i].c==0))) return 1;
        }
    return 0;
}
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;
        }
        // if (t==6)

        // for (int i=1;i<=n;i++)
        //     if (used[i])
        //         cout<<i<<"* "<<endl;
        for (int i=0;i<V.size ();i++)
            dfs (V[i],1);
        for (int i=0;i<V.size ();i++)
            if (deg[V[i]]==0) q.push (V[i]);
        if (t==6) cout<<"deg: "<<deg[1]<<endl;
        while (!q.empty ())
        {
            int u=q.front();
            cout<<u<<" ";
            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]}));
                    }
                }
        }
    }
}
signed main()
{
    scanf ("%lld",&t);
    while (t--)
    {
        cnt=0;
        memset (used,0,sizeof (used));
        memset (deg,0,sizeof (deg));
        scanf ("%lld%lld",&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 ("%lld%lld%lld%lld",&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,1)) printf ("FUck");
            memset (used,0,sizeof (used));
        }
        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
*/