shortestpath1.cpp

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

const int maxn = 2e5 + 5;
const long long inf = 1e18;
const int mod[3] = {1000000000 + 7, 1000000000 + 87, 1000000000 + 123};
vector<pair<int, int>> g[maxn], r[maxn];
long long d[maxn][2];
int dp[maxn][3][2];
int u[maxn], v[maxn], w[maxn];
bool vs[maxn];

void dijk(int s, vector<pair<int, int>> *g) {
    for (int i = 0; i < maxn; ++i)
        d[i][s] = inf;

    memset(vs, false, sizeof(vs));
    d[s][s] = 0;
    dp[s][0][s] = dp[s][1][s] = dp[s][2][s] = 1;
    priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;
    pq.emplace(0, s);

    while (!pq.empty()) {
        int x = pq.top().second; pq.pop();
        if (vs[x]) continue;
        vs[x] = true;

        for (int i = 0; i < (int)g[x].size(); ++i) {
            int u = g[x][i].first, w = g[x][i].second;
            if (d[u][s] > d[x][s] + w) {
                d[u][s] = d[x][s] + w;
                pq.emplace(d[u][s], u);
                for (int j = 0; j < 3; ++j)
                    dp[u][j][s] = dp[x][j][s];
            } else if (d[u][s] == d[x][s] + w) {
                for (int j = 0; j < 3; ++j)
                    (dp[u][j][s] += dp[x][j][s]) %= mod[j];
            }
        }
    }
}

int main() {
    int n, m; scanf("%d%d", &n, &m);

    for (int i = 0; i < m; ++i) {
        int u, v, d; scanf("%d%d%d", &u, &v, &d);
        --u, --v;
        g[u].emplace_back(v, d);
        r[v].emplace_back(u, d);

        ::u[i] = u;
        ::v[i] = v;
        ::w[i] = d;
    }

    dijk(0, g);
    dijk(1, r);

    printf("%lld\n", d[1][0]);
    printf("%d\n", dp[1][0][0]);

    int ans = 0;
    for (int i = 0; i < m; ++i) {
        if (d[u[i]][0] + w[i] + d[v[i]][1] != d[1][0])
            continue;

        bool uniq = true;
        for (int j = 0; j < 3; ++j)
            uniq &= dp[u[i]][j][0] * 1ll * dp[v[i]][j][1] % mod[j] == dp[1][j][0];

        ans += (int)uniq;
    }
    printf("%d\n", ans);
    return 0;
}