solution

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 510;
vector<int> pre[N];
int vis[N];
int map[510][510], dis[510], money[510][510];
int n, m, s, d;
const int inf=9999999;
vector<int> path, temppath;
int mincost = inf;
void dfs(int v)
{
    temppath.push_back(v);
    if (v == s)
    {
        int tempcost = 0;
        for (int i = temppath.size() - 1; i > 0; i--)
        {
            int id = temppath[i], nextid = temppath[i - 1];
            tempcost += money[id][nextid];
        }
        if (tempcost < mincost)
        {
            mincost = tempcost;
            path = temppath;
        }
        temppath.pop_back();
        return;
    }
    for (int i = 0; i < pre[v].size(); i++)
        dfs(pre[v][i]);
    temppath.pop_back();
}
int main()
{
    memset(dis, inf, sizeof dis);
    memset(map, inf, sizeof map);
    cin >> n >> m >> s >> d;
    for (int i = 0; i < m; i++)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        scanf("%d", &map[a][b]);
        map[b][a] = map[a][b];
        scanf("%d", &money[a][b]);
        money[b][a] = money[a][b];
    }
    pre[s].push_back(s);
    dis[s] = 0;
    for (int i = 0; i < n; i++)
    {
        int u = -1, minn = inf;
        for (int j = 0; j < n; j++)
        {
            if (vis[j] == false && dis[j] < minn)
            {
                u = j;
                minn = dis[j];
            }
        }
        if(u == -1) break;
        vis[u] = true;
        for(int v = 0; v < n; v++) {
            if(vis[v] == false && map[u][v] != 0x3f3f3f) {
                if(dis[v] > dis[u] + map[u][v]) {
                    dis[v] = dis[u] + map[u][v];
                    pre[v].clear();
                    pre[v].push_back(u);
                } else if(dis[v] == dis[u] + map[u][v]) {
                    pre[v].push_back(u);
                }
                  }
        }
    }
    dfs(d);
    for(int i = path.size() - 1; i >= 0; i--)
        printf("%d ", path[i]);
    printf("%d %d", dis[d], mincost);
}