30.

Dijkstra+dfs。主要是先用dijkstra搞出每个点的最短路径，以及记录下那些同样可以构成最短路径的前驱点在pre里。vector在这种情况下是非常好用的。然后就是从目的点往回深搜，我用的是一个栈记录路径，尤其要注意栈pop时要处理一些事，缺一不可。

#include <iostream>
#include <vector>
#include <algorithm>
#define Infinity 99999999

using namespace std;

bool visit[501];
int edge[501][501],cost[501][501],dist[501],path[501],totalmoney=Infinity,stack[501],sp=-1,money=0;
vector<int>pre[501];
int N,M,S,D;

void dfs(int u)
{
    stack[++sp]=u;
    if(u==S)
    {
        if(money<totalmoney)
        {
            memcpy(path,stack,501);
            totalmoney=money;
        }
        return ;
    }
    for(vector<int>::iterator p=pre[u].begin();p!=pre[u].end();p++)
    {
        money+=cost[u][*p];
        dfs(*p);
        //退栈时要注意三件小事
        stack[sp]=-1;
        sp--;
        money-=cost[u][*p];
    }
    return ;
}

int main()
{
    cin>>N>>M>>S>>D;
    fill(visit,visit+501,false);
    fill(edge[0],edge[0]+501*501,Infinity);
    fill(dist,dist+501,Infinity);
    fill(path,path+501,-1);
    fill(stack,stack+501,-1);
    for(int i=0;i<M;i++)
    {
        int city1,city2;
        cin>>city1>>city2;
        cin>>edge[city1][city2];
        edge[city2][city1]=edge[city1][city2];
        cin>>cost[city1][city2];
        cost[city2][city1]=cost[city1][city2];
    }

    //Dijkstra algorithm
    dist[S]=0;
    while(true)
    {
        int min=Infinity,u=-1;
        for(int j=0;j<N;j++)
        {
            if(visit[j]== false&&dist[j]<min)
            {
                min=dist[j];
                u=j;
            }
        }
        if(u==-1)break;
        visit[u]=true;
        for(int v=0;v<N;v++)
        {
            if(edge[u][v]<Infinity)
            {
                if(visit[v]==false&&dist[u]+edge[u][v]<dist[v])
                {
                    dist[v]=dist[u]+edge[u][v];
                    pre[v].clear();
                    pre[v].push_back(u);
                }
                else if(dist[u]+edge[u][v]==dist[v])
                {
                    pre[v].push_back(u);
                }
            }
        }
    }

    dfs(D);

    for(int i=500;i>=0;i--)
    {
        if(path[i]!=-1)
        {
            cout<<path[i]<<' ';
        }
    }
    cout<<dist[D]<<' '<<totalmoney;
}