https://pintia.cn/problem-sets/994805046380707840/exam/problems/994805073643683840?type=7&page=0

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> PII;
typedef vector<long long> VI;
#define rep(i,a,n) for (int i=a;i<=n;i++)
#define per(i,a,n) for (int i=a;i>=n;i--)
#define pb(i) push_back(i)
#define int long long
#define INF 0x3f3f3f3f
#define oz  998244353
#define endl '\n'
#define N 510
const int mod = 1e9 + 7;


int p[N], si[N];
int find(int x) {
    if (x == p[x])return p[x];
    p[x] = find(p[x]);
    return p[x];
}
//size[find(b)] += size[find(a)];
//p[find(a)] = find(b);


int n, m, s, d; // 城市数 边数 起始点 终点
int dis[N]; // 起始点到i的最短路
int sum[N]; // 起始点到i点最短情况下的最大救援队数量
int cnt[N]; // 起始点到i点最短路的条数
int pre[N]; // 记录最短路的路径
vector<PII> g[N]; // 邻接表存邻边和权值
bool vis[N]; // 访问数组
int a[N]; // 存城市的救援队数量

void dj() {

    priority_queue<PII, vector<PII>, greater<PII>> q; //存i和dis[i]

    memset(dis, 0x3f, sizeof dis);
    memset(pre, -1, sizeof pre);

    q.push({0, s});

    dis[s] = 0;
    cnt[s] = 1;
    sum[s] = a[s];


    while (!q.empty()) {
        int u = q.top().second;
        q.pop();

        if (vis[u])continue;

        vis[u] = 1;

        for (int i = 0; i < (int)g[u].size(); i++) {
            int v = g[u][i].first, w = g[u][i].second;

            if (dis[v] > dis[u] + w) {
                dis[v] = dis[u] + w;
                sum[v] = sum[u] + a[v];
                pre[v] = u;
                cnt[v] = cnt[u];

                q.push({dis[v], v});

            }

            else if (dis[v] == dis[u] + w) {
                cnt[v] += cnt[u];

                if (sum[v] < sum[u] + a[v]) {
                    sum[v] = sum[u] + a[v];
                    pre[v] = u;
                }
            }
        }


    }

}
void solve() {
    cin >> n >> m >> s >> d;
    s ++;
    d ++;

    for (int i = 1; i <= n; i++)cin >> a[i];

    while (m --) { //建图
        int u, v, w;
        cin >> u >> v >> w;
        u ++, v ++;
        g[u].push_back({v, w});
        g[v].push_back({u, w});
    }

    dj();



    cout << cnt[d] << " " << sum[d] << endl;

    stack<int> st;

    int p = d;
    while (p != -1) {
        st.push(p);
        p = pre[p];
    }

    while (st.size() > 1) {
        cout << st.top() -1 << " ";
        st.pop();
    }
    cout << st.top()-1 << endl;
    st.pop();


}

signed main() {

    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    int T = 1;
//  cin >> T;
    while (T --)

        solve();

    return 0;
}