QBSCHOOL

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

const int N = 5005;
const int oo = 1000111000;

typedef pair<ll, ll> ii;

int n, m;
vector<ii> a[N];
ll d[N], inc[N];

void dijkstra() {
    priority_queue<ii, vector<ii>, greater<ii>> pq;
    fill(d + 1, d + n + 1, oo);
    d[1] = 0;
    pq.push(ii(0, 1));

    while(!pq.empty()) {
        int u = pq.top().second;
        int du = pq.top().first;
        pq.pop();

        if(du != d[u]) continue;

        for(int i = 0; i < a[u].size(); i++) {
            int v = a[u][i].second;
            int uv = a[u][i].first;

            if(d[v] == d[u] + uv)
                inc[v] += inc[u];

            if(d[v]> d[u]+ uv) {
                d[v] = du + uv;
                pq.push(ii(d[v], v));
                inc[v] = inc[u];
            }
        }
    }
}

int main() {
    //freopen("QBSCHOOL.inp","r",stdin);
    //freopen("QBSCHOOL.out","w",stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> n >> m;
    for(int i = 1; i <= m; i++) {
        int k, p, q, w;
        cin >> k >> p >> q >> w;
        if(k == 1)
            a[p].push_back(ii(w, q));
        else {
            a[p].push_back(ii(w, q));
            a[q].push_back(ii(w, p));
        }
    }

    inc[1] = 1;
    dijkstra();

    cout << d[n] << ' ' << inc[n];

    return 0;
}