Hyperloop

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

int G[1010][1010];
int dist[1010], par[1010];
bool visited[1010];

int main()
{
    int n, m, z;
    scanf("%d%d%d", &n, &m, &z);
    int s, t;
    scanf("%d%d", &s, &t);
    while (m--) {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        if (z < w)
            G[u][v] = G[v][u] = w;
    }
    int q;
    scanf("%d", &q);

    for (int i = 0; i < n; ++i)
        dist[i] = 1e9;
    dist[s] = 0;
    while (true) {
        // find min node
        int mindist = 1e9, u = -1;
        for (int i = 0; i < n; ++i) {
            if (!visited[i] && dist[i] < mindist) {
                mindist = dist[i];
                u = i;
            }
        }
        if (u == -1) break;
        // set visit
        visited[u] = true;
        // update neighbors of u
        for (int v = 0; v < n; ++v) {
            if (G[u][v] && !visited[v] && dist[u]+G[u][v] < dist[v]) {
                dist[v] = dist[u]+G[u][v];
                par[v] = u;
            }
        }
    }
    if (!visited[t]) {
        printf("-1\n");
        return 0;
    }
    printf("%d\n", dist[t]);
    if (q == 1) return 0;

    int u = t;
    vector<int> ans;
    while (u != s) {
        ans.push_back(u);
        u = par[u];
    }
    ans.push_back(s);

    printf("%d\n", ans.size());
    for (int i = ans.size()-1; i >= 0; --i)
        printf("%d ", ans[i]);

    return 0;
}