#include <bits/stdc++.h>
#define INF 10000000000
#define ll long long int
#define pb push_back
#define mp make_pair
#define FOR(i, n) for (long long int i = 0; i < n; i++)
#define FORR(i, a, b) for (int i = a; i < b; i++)
// think about a question calmly, don't get panic to solve A fast
// if after 10 mins you are unable to think anything see dashboard
using namespace std;
void djk_fun(vector<vector<vector<int>>> &adj, int src, vector<int> &dis)
{
priority_queue<vector<int>, vector<vector<int>>, greater<vector<int>>> pq;
dis[src] = 0;
pq.push({{0, src}});
while (pq.size() > 0)
{
vector<int> vr = pq.top();
pq.pop();
int nod = vr[1];
for (int i = 0; i < adj[nod].size(); i++)
{
int neg = adj[nod][i][0], wt = adj[nod][i][1];
if (dis[nod] + wt < dis[neg])
{
dis[neg] = dis[nod] + wt;
pq.push({dis[neg], neg});
}
}
}
}
int short_path(vector<vector<vector<int>>> &adj, vector<vector<int>> &nh, int st, int en, int n)
{
int m = nh.size(), ans = INT_MAX;
// apply shortest path on src and dest
vector<int> dis_src(n + 1, 1e9);
vector<int> dis_dst(n + 1, 1e9);
djk_fun(adj, st, dis_src);
djk_fun(adj, en, dis_dst);
for (int i = 0; i < m; i++)
{
int n1 = nh[i][0], n2 = nh[i][1], wt = nh[i][2];
ans = min({ans, dis_src[n1] + wt + dis_dst[n2], dis_src[n2] + wt + dis_dst[n1]});
}
ans = min(ans, dis_src[en]);
if(ans > 1e9)
{
return -1;
}
return ans;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
ll n, m, st, en;
cin >> n >> m;
vector<vector<vector<int>>> adj(n + 1, vector<vector<int>>());
vector<vector<int>> nh;
// construct graph using state highways
for (int i = 0; i < m; i++)
{
int u, v, st, nt;
cin >> u >> v >> st >> nt;
nh.pb({u, v, nt});
adj[u].pb({v, st});
adj[v].pb({u, st});
}
cin >> st >> en;
cout << short_path(adj, nh, st, en, n) << endl;
return 0;
}
Comments