1 #include <algorithm>  2 #include <iostream>  3 #include <iomanip>  4 #include <cstring>  5 #include <climits>  6 #include <complex>  7 #include <fstream>  8 #include <cassert>  9 #include <cstdio> 10 #include <bitset> 11 #include <vector> 12 #include <deque> 13 #include <queue> 14 #include <stack> 15 #include <ctime> 16 #include <set> 17 #include <map> 18 #include <cmath> 19   20 using namespace std; 21 #define fr first 22 #define sc second 23 #define cl clear 24 #define BUG puts("here!!!") 25 #define W(a) while(a--) 26 #define pb(a) push_back(a) 27 #define Rint(a) scanf("%d", &a) 28 #define Rll(a) scanf("%I64d", &a) 29 #define Rs(a) scanf("%s", a) 30 #define Cin(a) cin >> a 31 #define FRead() freopen("in", "r", stdin) 32 #define FWrite() freopen("out", "w", stdout) 33 #define Rep(i, len) for(int i = 0; i < (len); i++) 34 #define For(i, a, len) for(int i = (a); i < (len); i++) 35 #define Cls(a) memset((a), 0, sizeof(a)) 36 #define Clr(a, p) memset((a), (p), sizeof(a)) 37 #define Full(a) memset((a), 0x7f7f7f, sizeof(a)) 38 #define lrt rt << 1 39 #define rrt rt << 1 | 1 40 #define pi 3.14159265359 41 #define RT return 42 #define lowbit(p) p & (-p) 43 #define onenum(p) __builtin_popcount(p) 44 typedef long long LL; 45 typedef long double LD; 46 typedef unsigned long long ULL; 47 typedef pair<int, int> pii; 48 typedef pair<string, int> psi; 49 typedef pair<LL, LL> pll; 50 typedef map<string, int> msi; 51 typedef vector<int> vi; 52 typedef vector<LL> vl; 53 typedef vector<vl> vvl; 54 typedef vector<bool> vb; 55   56 const int inf = 1e18; 57 const int maxn = 100100; 58 typedef struct Edge { 59     int u, v, w, c, next; 60     Edge() { next = -1; } 61     Edge(int uu, int vv, int ww, int cc) : u(uu), v(vv), w(ww), c(cc) { next = -1; } 62 }Edge; 63 typedef struct P { 64     int id, w; 65     P() {} 66     P(int i, int ww) : id(i), w(ww) {} 67     bool operator< (const P& a) const { 68         return w > a.w; 69     } 70 }P; 71 int head[maxn]; 72 Edge edge[maxn*2]; 73 bool vis[maxn*2]; 74 LL dis[maxn*2]; 75 int n, m, u, v, w, c; 76 int cnt; 77   78 void init() { 79     Clr(head, -1); Clr(edge, -1); 80     cnt = 0; 81 } 82   83 void adde(int u, int v, int c, int w) { 84   edge[cnt].u = u; edge[cnt].v = v; edge[cnt].c = c; edge[cnt].w = w;   85   edge[cnt].next = head[u]; head[u] = cnt++; 86 } 87   88 LL dij(int s, int t) { 89     LL ret = inf; 90     Cls(vis); 91     Rep(i, cnt) dis[i] = inf; 92     priority_queue<P> pq; 93     for(int i = head[s]; ~i; i=edge[i].next) { 94         dis[i] = edge[i].w; 95         pq.push(P(i, dis[i])); 96     } 97     while(!pq.empty()) { 98         P tmp = pq.top(); pq.pop(); 99         int id = tmp.id;100         if(vis[id]) continue;101         vis[id] = 1;102         u = edge[id].v;103         if(u == t) ret = min(ret, dis[id]);104         for(int i = head[u]; ~i; i=edge[i].next) {105             v = edge[i].v;106             if(!vis[i] && dis[i] > dis[id] + edge[i].w + abs(edge[i].c - edge[id].c)) {107                 dis[i] = dis[id] + edge[i].w + abs(edge[i].c - edge[id].c);108                 pq.push(P(i, dis[i]));109             }110         }111     }112     return ret;113 }114  115 int main() {116     // FRead();117     while(~Rint(n)&&~Rint(m)) {118         init();119         Rep(i, m) {120             scanf("%d%d%d%d",&u,&v,&c,&w);121             adde(u, v, c, w);122             adde(v, u, c, w);123         }124         cout << dij(1, n) << endl;125     }126     RT 0;127 }