#include <bits/stdc++.h>
using namespace std;

#define N 100005
using i64 = long long;

int n, m, vis[N];
i64 dis1[N], dis2[N];
vector<array<int, 3>> G[N], H[N];
vector<pair<int, int>> adj[N], sccadj[N];

int tot, sccnum, dfn[N], low[N], in_sta[N], belong[N];
stack<int> sta;
void tarjan(int cur)
{
    dfn[cur] = low[cur] = ++tot;
    in_sta[cur] = 1;
    sta.push(cur);
    for (const auto [i, _] : adj[cur])
    {
        if (dfn[i] == 0)
        {
            tarjan(i);
            low[cur] = min(low[cur], low[i]);
        }
        else if (in_sta[i])
            low[cur] = min(low[cur], dfn[i]);
    }
    if (low[cur] == dfn[cur])
    {
        sccnum++;
        int x;
        do
        {
            x = sta.top();
            sta.pop();
            belong[x] = sccnum;
            in_sta[x] = 0;
        } while (x != cur);
    }
}

void solve()
{
    cin >> n >> m;
    for (int i = 1, u, v, x, y; i <= m; i++)
    {
        cin >> u >> v >> x >> y;
        G[u].push_back({v, x, y});
        H[v].push_back({u, x, y});
    }

    for (int i = 1; i <= n; i++)
        vis[i] = 0, dis1[i] = 1e18;
    priority_queue<pair<i64, int>> que;
    que.push({0, 1});
    dis1[1] = 0;
    while (!que.empty())
    {
        int cur = que.top().second;
        que.pop();
        if (vis[cur])
            continue;
        vis[cur] = 1;
        for (auto [i, val, _] : G[cur])
        {
            if (dis1[i] > dis1[cur] + val)
            {
                dis1[i] = dis1[cur] + val;
                que.push({-dis1[i], i});
            }
        }
    }

    for (int i = 1; i <= n; i++)
        vis[i] = 0, dis2[i] = 1e18;
    que.push({0, n});
    dis2[n] = 0;
    while (!que.empty())
    {
        int cur = que.top().second;
        que.pop();
        if (vis[cur])
            continue;
        vis[cur] = 1;
        for (auto [i, val, _] : H[cur])
        {
            if (dis2[i] > dis2[cur] + val)
            {
                dis2[i] = dis2[cur] + val;
                que.push({-dis2[i], i});
            }
        }
    }

    i64 mindis = dis1[n];
    cout << dis1[n] << ' ';
    vector<i64> ans(n + 1);
    vector<int> degree(n + 1);
    for (int i = 1; i <= n; i++)
        for (auto &[j, val, h] : G[i])
            if (dis1[i] + val + dis2[j] == mindis)
                adj[i].push_back({j, h});
    for (int i = 1; i <= n; i++)
        if (!dfn[i])
            tarjan(i);
    for (int i = 1; i <= n; i++)
        for (auto &[j, val] : adj[i])
            if (belong[i] != belong[j])
                sccadj[belong[i]].push_back({belong[j], val}), degree[belong[j]]++;

    queue<int> tque;
    tque.push(belong[1]);
    while (!tque.empty())
    {
        int cur = tque.front();
        tque.pop();
        for (auto [i, val] : sccadj[cur])
        {
            ans[i] = max(ans[i], ans[cur] + val);
            if (!--degree[i])
                tque.push(i);
        }
    }
    cout << ans[belong[n]] << '\n';
    tot = sccnum = 0;
    for (int i = 1; i <= n; i++)
    {
        G[i].clear(), H[i].clear(), adj[i].clear();
        sccadj[i].clear();
        dfn[i] = belong[i] = low[i] = 0;
    }
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
    cin >> t;
    while (t--)
        solve();
}