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

#define int long long
const int M = 998244353;
const int INF = 1e18;

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

    vector<vector<int>> adj(n, vector<int>(n, INF));
    while (m--)
    {
        int u, v, w;
        cin >> u >> v >> w;
        u--, v--;
        adj[u][v] = w;
    }

    int mincyclen = INF, cntmncyc = 0;
    for (int st = 0; st < n; st++)
    {
        vector<int> dist(n, INF);
        vector<int> cnt(n);
        dist[st] = 0;
        cnt[st] = 1;
        vector<bool> vis(n);
        for (int _ = 0; _ < n - st; _++)
        {
            int pick = st;
            for (int i = st; i < n; i++)
            {
                if (vis[i] < vis[pick] || (!vis[i] && dist[i] < dist[pick]))
                {
                    pick = i;
                }
            }

            vis[pick] = 1;
            for (int i = st; i < n; i++)
            {
                if (dist[pick] + adj[pick][i] < dist[i])
                {
                    dist[i] = dist[pick] + adj[pick][i];
                    cnt[i] = cnt[pick];
                }
                else if (dist[pick] + adj[pick][i] == dist[i])
                {
                    cnt[i] += cnt[pick];
                    cnt[i] %= M;
                }
            }
        }

        int cyclen = INF, cntcyc = 0;
        for (int i = st + 1; i < n; i++)
        {
            if (dist[i] + adj[i][st] < cyclen)
            {
                cyclen = dist[i] + adj[i][st];
                cntcyc = cnt[i];
            }
            else if (dist[i] + adj[i][st] == cyclen)
            {
                cntcyc += cnt[i];
                cntcyc %= M;
            }
        }

        if (cyclen < mincyclen)
        {
            mincyclen = cyclen;
            cntmncyc = cntcyc;
        }
        else if (cyclen == mincyclen)
        {
            cntmncyc += cntcyc;
            cntmncyc %= M;
        }
    }

    if (mincyclen >= INF)
    {
        cout << "-1 -1\n";
    }
    else
    {
        cout << mincyclen << ' ' << cntmncyc << '\n';
    }
}

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

    int t;
    cin >> t;
    while (t--)
    {
        solve();
    }

    return 0;
}