1 #include <bits/stdc++.h> 2 using namespace std; 3 #define N 100010 4 typedef long long LL; 5 const LL INF = 1000000000000000000LL; 6 struct Edge { 7     int u, v, nxt, w, c; 8 } edge[N*2]; 9 struct Node {10     LL d; int id;11     bool operator < (const Node &rhs) const {12         return d > rhs.d;13     }14 };15 int head[N], tot, n, m;16 bool vis[N*2];17 LL dis[N*2];18 19 void Add(int u, int v, int w, int id) {20     edge[tot] = (Edge) { u, v, head[u], w, id}; head[u] = tot++;21     edge[tot] = (Edge) { v, u, head[v], w, id}; head[v] = tot++;22 }23 24 LL Dijkstra() {25     for(int i = 0; i < tot; i++) dis[i] = INF;26     memset(vis, 0, sizeof(vis));27     LL ans = INF;28     priority_queue<Node> que;29     while(!que.empty()) que.pop();30 31     for(int i = head[1]; ~i; i = edge[i].nxt)32         que.push((Node) {edge[i].w, i}), dis[i] = edge[i].w;33     while(!que.empty()) {34         Node now = que.top(); que.pop();35         int pree = now.id; LL pred = now.d;36         if(vis[pree]) continue; vis[pree] = 1;37         int u = edge[pree].v;38         if(u == n && ans > pred) ans = pred;39         for(int i = head[u]; ~i; i = edge[i].nxt) {40             int nowe = i;41             LL nowd = dis[pree] + edge[nowe].w + abs(edge[nowe].c - edge[pree].c);42             if(nowd < dis[nowe] && !vis[nowe]) {43                 dis[nowe] = nowd;44                 que.push((Node) { nowd, nowe });45             }46         }47     }48     return ans;49 }50 51 int main() {52     while(~scanf("%d%d", &n, &m)) {53         memset(head, -1, sizeof(head)); tot = 0;54         for(int i = 1; i <= m; i++) {55             int u, v, c, w;56             scanf("%d%d%d%d", &u, &v, &c, &w);57             Add(u, v, w, c);58         }59         printf("%lld\n", Dijkstra());60     }61     return 0;62 }63 /*64 3 365 1 2 1 166 2 3 2 167 1 3 1 168 3 369 1 2 1 170 2 3 2 171 1 3 1 1072 3 273 1 2 1 174 2 3 1 175 */