Description

 Bobo 居住在大城市 ICPCCamp。

ICPCCamp 有 n 个地铁站，用 1,2,…,n 编号。 m 段双向的地铁线路连接 n 个地铁站，其中第 i 段地铁属于 c

_i 号线，位于站 a

_i,b

_i 之间，往返均需要花费 t

_i 分钟（即从 a

_i 到 b

_i 需要 t

_i 分钟，从 b

_i 到 a

_i 也需要 t

_i 分钟）。

众所周知，换乘线路很麻烦。如果乘坐第 i 段地铁来到地铁站 s，又乘坐第 j 段地铁离开地铁站 s，那么需要额外花费 |c

_i-c

_j | 分钟。注意，换乘只能在地铁站内进行。

Bobo 想知道从地铁站 1 到地铁站 n 所需要花费的最小时间。

Input

输入包含不超过 20 组数据。

每组数据的第一行包含两个整数 n,m (2≤n≤10

⁵,1≤m≤10

⁵).

接下来 m 行的第 i 行包含四个整数 a

_i,b

_i,c

_i,t

_i (1≤a

_i,b

_i,c

_i≤n,1≤t

_i≤10

⁹).

保证存在从地铁站 1 到 n 的地铁线路（不一定直达）。

Output

对于每组数据，输出一个整数表示要求的值。

Sample Input

3 31 2 1 12 3 2 11 3 1 13 31 2 1 12 3 2 11 3 1 103 21 2 1 12 3 1 1

Sample Output

132

Hint

以边建图，通过边的权值大小进行bfs不断更新

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std;#define MAXN 100010#define INF 0x3ffffffftypedef long long ll;struct edge{ ll from, to, ci,w;};struct node{ ll x, sum; int fa;//记录连接了几个点 friend bool operator <(node n1, node n2) { return n1.sum>n2.sum; }};ll ans, n, m;vector
          
           G[MAXN];vector
           
            edges;priority_queue
            
             q;int vis[MAXN * 2];void addedge(ll x, ll y, ll ci, ll w){ edge v = { x, y, ci, w }; edges.push_back(v);//边 G[x].push_back(edges.size() - 1);//点}void bfs(){ node a = { 1, 0, -1 }; q.push(a); while (!q.empty()) { a = q.top(); q.pop(); if (a.x == n) { ans = a.sum; return; } if (a.fa != -1 && vis[a.fa]) continue; vis[a.fa] = 1; for (int i = 0; i < G[a.x].size(); i++) { node b = a; edge v = edges[G[a.x][i]]; b.x = v.to; b.fa = G[a.x][i]; b.sum += v.w; if (a.fa >= 0) { b.sum += abs(edges[a.fa].ci - v.ci); } q.push(b); } }}int main(){ while (~scanf("%lld%lld", &n, &m)) { for (int i = 0; i <= n; i++) G[i].clear(); edges.clear(); for (int i = 1; i <= m; i++) { ll x, y, ci, w; scanf("%lld%lld%lld%lld", &x, &y, &ci, &w); addedge(x, y, ci, w); addedge(y, x, ci, w); } ans = INF; memset(vis, 0, sizeof(vis)); while (!q.empty()) q.pop(); bfs(); cout << ans<< endl; } return 0;}/********************************************************************** Problem: 1808 User: leo6033 Language: C++ Result: AC Time:1844 ms Memory:19208 kb**********************************************************************/