Travel plan

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

const int Max=510;
const int INF=INT_MAX;

int n,m,s,t,sum=INF;
vector<int> pre[Max];
vector<int> path,temp;
int G[Max][Max],cost[Max][Max];
int dis[Max];
bool visit[Max];

void Dijistra() {
	fill(dis,dis+Max,INF);
	dis[s]=0;
	for(int i=0; i<n; i++) {
		int u=-1,Min=INF;
		for(int j=0; j<n; j++) {
			if(Min>dis[j]&&!visit[j]) {
				Min=dis[j];
				u=j;
			}
		}
		if(u==-1) return;
		visit[u]=1;
		for(int v=0; v<n; v++) {
			if(!visit[v]&&G[u][v]!=INF) {
				if(dis[v]>dis[u]+G[u][v]) {
					dis[v]=dis[u]+G[u][v];
					pre[v].clear();
					pre[v].emplace_back(u);
				} else if(dis[v]==dis[u]+G[u][v]) {
					pre[v].emplace_back(u);
				}
			}
		}
	}
}

void DFS(int t) {
	if(t==s) {
		temp.emplace_back(t);
		int value=0;
		for(int i=temp.size()-1; i>0; i--) {
			int id=temp[i],Next=temp[i-1];
			value+=cost[id][Next];
		}
		if(value<sum) {
			sum=value;
			path=temp;
		}
		temp.pop_back();
		return ;
	}
	temp.emplace_back(t);
	for(int i=0; i<pre[t].size(); i++) {
		DFS(pre[t][i]);
	}
	temp.pop_back();
}

int main() {
	scanf("%d %d %d %d",&n,&m,&s,&t);
	int from,to;
	fill(G[0],G[0]+Max*Max,INF);
	fill(cost[0],cost[0]+Max*Max,INF);
	for(int i=0; i<m; i++) {
		scanf("%d %d",&from,&to);
		scanf("%d %d",&G[from][to],&cost[from][to]);
        G[to][from]=G[from][to];
        cost[to][from]=cost[from][to];
	}
	Dijistra();
	DFS(t);
	int k=path.size();
	for(int i=k-1; i>=0; i--) {
		printf("%d ",path[i]);
	}
	printf("%d %d\n",dis[t],sum);
	return 0;
}