#include <bits/stdc++.h>
using namespace std;
const long long inf = 0x3f3f3f3f3f3f3f3fll;
const int N = 200000, M = 300000;
struct line
{
    int from;
    int to;
    long long v;
    long long gain;
    int next;
};
struct line que[M + 5];
struct edge
{
    int from;
    int to;
    long long gain;
    edge(int _from, int _to, long long _gain)
    {
        from = _from;
        to = _to;
        gain = _gain;
    }
};
int cnt, headers[N + 5];
void add(int from, int to, long long v, long long gain)
{
    cnt++;
    que[cnt].from = from;
    que[cnt].to = to;
    que[cnt].v = v;
    que[cnt].gain = gain;
    que[cnt].next = headers[from];
    headers[from] = cnt;
}
vector<edge> graph[N + 5], newgraph[N + 5];
struct node
{
    int id;
    long long dis;
    node(int _id, long long _dis)
    {
        id = _id;
        dis = _dis;
    }
    bool operator<(const node &b)const
    {
        return dis > b.dis;
    }
};
int n, m;
long long dis[N + 5];
bool vis[N + 5];
void dijkstra(int s, int t)
{
    for (int i = 1; i <= n;i++)
    {
        dis[i] = inf;
        vis[i] = 0;
    }
    dis[s] = 0;
    priority_queue<node> q;
    q.emplace(s, 0);
    while (!q.empty())
    {
        auto tp = q.top();
        q.pop();
        if (vis[tp.id])
            continue;
        vis[tp.id] = 1;
        for (int i = headers[tp.id]; i; i = que[i].next)
            if(dis[que[i].to] > dis[tp.id] + que[i].v)
            {
                dis[que[i].to] = dis[tp.id] + que[i].v;
                q.emplace(que[i].to, dis[que[i].to]);
            }
    }
}
int dfn[N + 5], low[N + 5], ind, col[N + 5], tot;
stack<int> s;
void tarjan(int u)
{
    dfn[u] = low[u] = ++ind;
    s.push(u);
    vis[u] = 1;
    for (auto i : graph[u])
        if(!dfn[i.to])
        {
            tarjan(i.to);
            low[u] = min(low[u], low[i.to]);
        }
        else if (vis[i.to])
            low[u] = min(dfn[i.to], low[u]);
    if (low[u] == dfn[u])
    {
        tot++;
        while (s.top() != u)
        {
            col[s.top()] = tot;
            vis[s.top()] = 0;
            s.pop();
        }
        col[u] = tot;
        vis[u] = 0;
        s.pop();
    }
}
int deg[N + 5];
long long f[N + 5];
void topo(int s)
{
    queue<int> q;
    for (int i = 1; i <= tot;i++)
        if(!deg[i])
            q.push(i);
    while(!q.empty())
    {
        int tp = q.front();
        q.pop();
        for (auto i : newgraph[tp])
        {
            deg[i.to]--;
            f[i.to] = max(f[i.to], f[tp] + i.gain);
            if(!deg[i.to])
                q.push(i.to);
        }
    }
}
int main()
{
    int t;
    scanf("%d", &t);
    while(t--)
    {
        scanf("%d%d", &n, &m);
        for (int i = 1, u, v; i <= m; i++)
        {
            long long dis, gain;
            scanf("%d%d%lld%lld", &u, &v, &dis, &gain);
            add(u, v, dis, gain);
        }
        dijkstra(1, n);
        for (int i = 1; i <= n; i++)
            for (int j = headers[i]; j; j = que[j].next)
                if(dis[que[j].to] == dis[i] + que[j].v)
                    graph[i].emplace_back(i, que[j].to, que[j].gain);
        for (int i = 1; i <= n;i++)
            vis[i] = 0;
        printf("%lld ", dis[n]);
        for (int i = 1; i <= n;i++)
            if(!dfn[i])
                tarjan(i);
        for (int i = 1; i <= n;i++)
            for (auto j : graph[i])
                if (col[i] != col[j.to])
                    newgraph[col[i]].emplace_back(col[i], col[j.to], j.gain);
        for (int i = 1; i <= tot;i++)
            for (auto j : newgraph[i])
                deg[j.to]++;
        topo(col[1]);
        printf("%lld\n", f[col[n]]);
        for (int i = 1; i <= n; i++)
        {
            graph[i].clear();
            newgraph[i].clear();
            headers[i] = dfn[i] = low[i] = col[i] = deg[i] = f[i] = 0;
        }
        while(!s.empty())
            s.pop();
        cnt = ind = tot = 0;
    }
    return 0;
}