stablegradients/pie-gem5-bysrc huggingface dataset:
// Original C++ solution (slower):
/*********************

*  Author: xuziyuan  * 

*********************/



#include <bits/stdc++.h>



#define rt0 return 0

#define rep(i,n) for(int i=0;i<n;i++)

#define repn(i,n) for(int i=1;i<=n;i++)

#define replet(c) for(char c='a';c<='z';c++) 

#define LL long long

#define pii pair <int,int>

#define pb push_back

#define fi first

#define se second

#define mpr make_pair

#define sqr(a) ((a)*(a))



using namespace std;



const LL MOD=1e9+7;



LL n,t,dp[110][10010],all=1,ans=0;



int main()

{

	cin>>n>>t;

	rep(i,n-1) all=all*(t+1)%MOD;

	all=all*(t+1)*t/2*n%MOD;

	dp[n][0]=1;

	for(int i=n;i>0;i--)

	{

		rep(j,10005)

		{

			rep(k,t+1)

			{

				if(dp[i][j]==0) continue;

				if(k<=i) dp[i-1][j+(j+k)/i]=(dp[i-1][j+(j+k)/i]+dp[i][j])%MOD;

				else dp[i-1][j]=(dp[i-1][j]+dp[i][j])%MOD;

			}

		}

	}

	repn(i,10003) ans=(ans+i*dp[0][i])%MOD;

	cout<<(all-ans+MOD)%MOD<<endl;

	rt0;

}

// Optimized solution to the same problem (faster):
/*********************

*  Author: xuziyuan  * 

*********************/



#include <bits/stdc++.h>



#define rt0 return 0

#define rep(i,n) for(int i=0;i<n;i++)

#define repn(i,n) for(int i=1;i<=n;i++)

#define replet(c) for(char c='a';c<='z';c++) 

#define LL long long

#define pii pair <int,int>

#define pb push_back

#define fi first

#define se second

#define mpr make_pair

#define sqr(a) ((a)*(a))



using namespace std;



const LL MOD=1e9+7;



LL n,t,dp[110][10010],all=1,ans=0;



int main()

{

	cin>>n>>t;

	rep(i,n-1) all=all*(t+1)%MOD;

	all=all*(t+1)*t/2*n%MOD;

	if(n==t)

	{

		dp[n-1][1]=1;

		dp[n-1][0]=t;

	}

	else dp[n-1][0]=t+1;

	for(int i=n-1;i>0;i--)

	{

		rep(j,10005)

		{

			if(dp[i][j]==0) continue;

			rep(k,t+1)

			{

				if(k<=i) dp[i-1][j+(j+k)/i]=(dp[i-1][j+(j+k)/i]+dp[i][j])%MOD;

				else dp[i-1][j]=(dp[i-1][j]+dp[i][j])%MOD;

			}

		}

	}

	repn(i,10003) ans=(ans+i*dp[0][i])%MOD;

	cout<<(all-ans+MOD)%MOD<<endl;

	rt0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>

using namespace std;



#define REP(i,p,n) for(ll i=p;i<ll(n);++i)

#define rep(i,n) REP(i,0,n)



using ll = long long;

using pll = pair<ll, ll>;



const ll MAXN = 1002;

ll C[MAXN][MAXN];



int main()

{

    ll H, W;

    cin >> H >> W;



    ll CH, CW, DH, DW;

    cin >> CH >> CW >> DH >> DW;

    --CH;

    --CW;

    --DH;

    --DW;



    vector<string> S(H);

    rep (i, H) { cin >> S[i]; }



    rep (x, MAXN) rep (y, MAXN) { C[x][y] = MAXN * MAXN; }



    using Node = tuple<ll, ll, ll>;

    priority_queue<Node, vector<Node>, greater<Node> > Q;



    const auto insert = [&](ll xx, ll yy, ll newCost)

    {

        if (xx < 0 || W <= xx) { return; }

        if (yy < 0 || H <= yy) { return; }

        if (S[yy][xx] == '#') { return; }

        if (C[yy][xx] <= newCost) { return; }



        C[yy][xx] = newCost;

        Q.emplace(newCost, xx, yy);

    };



    insert(CW, CH, 0);



    ll ans = -1;



    while (!Q.empty())

    {

        const auto node = Q.top();

        Q.pop();



        const auto cost = get<0>(node);

        const auto cx = get<1>(node);

        const auto cy = get<2>(node);



        if (cx == DW && cy == DH) { ans = cost; break; }



        insert(cx - 1, cy, cost);

        insert(cx + 1, cy, cost);

        insert(cx, cy - 1, cost);

        insert(cx, cy + 1, cost);



        for (ll dx=-2;dx<=2;++dx)

        for (ll dy=-2;dy<=2;++dy)

        {

            insert(cx + dx, cy + dy, cost + 1);

        }

    }

    cout << ans << endl;



    return 0;

}


// Optimized solution to the same problem (faster):
#include <bits/stdc++.h>

using namespace std;



int main()

{

    int H, W, CH, CW, DH, DW;

    cin >> H >> W >> CH >> CW >> DH >> DW;

    --CH;

    --CW;

    --DH;

    --DW;



    vector<string> S(H);

    for (int i=0;i<H;++i) { cin >> S[i]; }



    vector<int> Cost(H * W, 1000001);

    deque< pair<int, int> > Q;



    const auto insert = [&](int x, int y, int cost, int extraCost)

    {

        if (x < 0 || W <= x || y < 0 || H <= y) { return; }

        if (S[y][x] == '#') { return; }



        const auto newCost = cost + extraCost;

        if (Cost[x + y * W] <= newCost) { return; }

        Cost[x + y * W] = newCost;



        if (extraCost == 0) { Q.emplace_front(x, y); }

        else                { Q.emplace_back(x, y); }

    };



    insert(CW, CH, 0, 0);



    int ans = -1;



    while (!Q.empty())

    {

        const auto x = Q.front().first;

        const auto y = Q.front().second;

        Q.pop_front();



        const auto cost = Cost[x + y * W];

        if (x == DW && y == DH) { ans = cost; break; }



        insert(x - 1, y, cost, 0);

        insert(x + 1, y, cost, 0);

        insert(x, y - 1, cost, 0);

        insert(x, y + 1, cost, 0);



        for (int dx=-2;dx<=2;++dx)

        for (int dy=-2;dy<=2;++dy)

        {

            insert(x + dx, y + dy, cost, 1);

        }

    }



    cout << ans << endl;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include "bits/stdc++.h"

#include "sstream"

#define quick ios_base::sync_with_stdio(false);cin.tie(NULL);

using namespace std;

const int N=1e5+1;

int arr[100];

int main() {

    quick

int n; cin>>n; long long ans=LONG_LONG_MAX;

for(int i=0;i<n;i++){cin>>arr[i];}

for(int i=0;i<=1e4;i++){

    long long sum=0;

for(int j=0;j<n;j++){

    sum+=(arr[j]-i)*(arr[j]-i);

}

if(sum<ans){ans=sum;}

}

cout<<ans;

}

// Optimized solution to the same problem (faster):
#include<bits/stdc++.h>

using namespace std;

typedef long long int ll;

int main()

{

    ll n,c=0,t=0,b,s=0,f,g,d=0,x=0;

    cin>>n;

    ll a[n+10];

    for(int i = 0;i < n;i++)

    {

        cin>>a[i];

        s += a[i];

    }



    f = ceil(s*1.0/n);

    //cout<<f<<endl;

    g = (s/n);

    //cout<<g<<endl;





    for(int i = 0;i < n;i++)

    {

        t = abs(f-a[i]);

        t = t*t;

        c += t;

        //cout<<c<<endl;

    }

    for(int i = 0;i < n;i++)

    {

        d = abs(g-a[i]);

        d = d*d;

        x += d;

        //cout<<c<<endl;

    }

    cout<<min(c,x)<<endl;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <queue>

#include <vector>

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#include <iostream>

#include <algorithm>

const int INF=0x3f3f3f3f;

using namespace std;

struct edge{

    int to,cost,w;

};

int V,d[10005],dis[10005];

vector<edge> G[20005];

typedef pair<int,int> P;

void dijkstra(int s){

    int i,v;

	priority_queue<P,vector<P>,greater<P> >que;

	fill(d,d+V+1,INF);

	fill(dis,dis+V+1,INF);

	d[s]=dis[s]=0;

	que.push(P(0,s));

	while(!que.empty()){

		P p=que.top(); que.pop();

		v=p.second;

		if(d[v]<p.first)

        continue;

		for(i=0;i<G[v].size();i++){

			edge e=G[v][i];

			if(d[e.to]>d[v]+e.cost){

				d[e.to]=d[v]+e.cost;

                dis[e.to]=e.w;

				que.push(P(d[e.to],e.to));

			}

			else if(d[e.to]==d[v]+e.cost)

            dis[e.to]=min(dis[e.to],e.w);

		}

	}

}

int main(){

    int m,st,en,i,j,x,y,z,q,ans;

    edge temp;

    while(scanf("%d%d",&V,&m)!=EOF&&(V||m)){

        for(i=0;i<=V;i++)

        G[i].clear();

        for(i=0;i<m;i++){

            scanf("%d%d%d%d",&x,&y,&z,&q);

            temp.to=y;temp.cost=z;temp.w=q;

            G[x].push_back(temp);

            temp.to=x;

            G[y].push_back(temp);

        }

        dijkstra(1);

        ans=0;

        for(i=1;i<=V;i++)

        ans+=dis[i];

        printf("%d\n",ans);

    }

    return 0;

}

// Optimized solution to the same problem (faster):
#include <cstdio>

#include <cstring>

#include <algorithm>



using namespace std;



constexpr int maxN = 10005;

constexpr int maxM = 400005;



int N, M;



int adj[maxN], gto[maxM], gnxt[maxM], length[maxM], cost[maxM], e;

void add_edge(int u, int v, int d, int c) {

    gto[e] = v; length[e] = d; cost[e] = c; gnxt[e] = adj[u]; adj[u] = e++;

}



void print_edge(int s) {

    printf("%d:", s);

    for (int e = adj[s]; ~e; e = gnxt[e])

        printf(" %d", gto[e]);

    putchar('\n');

}



int dis[maxN], pre[maxN];

int qu[maxN], qh, qt; bool inq[maxN];

void bellman_ford(int s) {

    memset(dis, 0x3f, sizeof dis); dis[s] = 0;

    for (inq[qu[qh = qt = 0] = s] = 1; qh <= qt; inq[qu[qh++ % N]] = 0)

        for (int u = qu[qh % N], e = adj[u], v = gto[e]; ~e; v = gto[e = gnxt[e]])

            if (dis[v] > dis[u] + length[e]) {

                dis[v] = dis[u] + length[e];

                pre[v] = cost[e];

                if (!inq[v]) inq[qu[++qt % N] = v] = 1;

            } else if (dis[v] == dis[u] + length[e]) {

                pre[v] = min(pre[v], cost[e]);

            }

}



int main() {

    while (~scanf("%d%d", &N, &M) && (N || M)) {

        memset(adj, -1, sizeof adj);

        for (int i = 0; i != M; ++i) {

            int u, v, d, c; scanf("%d%d%d%d", &u, &v, &d, &c);

            add_edge(u, v, d, c); add_edge(v, u, d, c);

        }

        bellman_ford(1);

        long long ans = 0;

        for (int i = 1; i <= N; ++i) ans += pre[i];

        printf("%lld\n", ans);

    }

    return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>

using namespace std;



typedef long long ll;

const int N = 10005;

const int M = 1000000007;



int n, m;

typedef int wtype;

struct Edge { int v; wtype d, c; };

vector<Edge> e[N];

wtype dist[N], cost[N];

int pre[N];

bool vis[N];

int SPFA(int src) {

  memset(dist, 0x3f, sizeof(dist)); dist[src] = 0;

  memset(cost, 0x3f, sizeof(cost)); cost[src] = 0;

  memset(vis, 0, sizeof(vis)); vis[src] = true;

  stack<int> que; que.push(src);

  while (!que.empty()) {

    int u = que.top(); que.pop();

    vis[u] = false;

    for (int i = 0; i < (int)e[u].size(); i++) {

      int v = e[u][i].v; wtype d = e[u][i].d, c = e[u][i].c;

      if (dist[v] > dist[u] + d || (dist[v] == dist[u] + d && cost[v] != 0x3f3f3f3f && cost[v] > c)) {

        dist[v] = dist[u] + d; cost[v] = c;

        if (!vis[v]) { vis[v] = true; que.push(v); }

      }

    }

  }

  int ret = 0;

  for (int i = 1; i <= n; i++) { ret += cost[i]; }

  return ret;

}



int main() {

  while (scanf("%d%d", &n, &m), n) {

    for (int i = 1; i <= n; i++) { e[i].clear(); }

    for (int i = 0, u, v, d, c; i < m; i++) {

      scanf("%d%d%d%d", &u, &v, &d, &c);

      e[u].push_back((Edge) {v, d, c});

      e[v].push_back((Edge) {u, d, c});

    }

    printf("%d\n", SPFA(1));

  }

}

// Optimized solution to the same problem (faster):
#include <cstdio>

#include <cstring>

#include <algorithm>



using namespace std;



constexpr int maxN = 10005;

constexpr int maxM = 400005;



int N, M;



int adj[maxN], gto[maxM], gnxt[maxM], length[maxM], cost[maxM], e;

void add_edge(int u, int v, int d, int c) {

    gto[e] = v; length[e] = d; cost[e] = c; gnxt[e] = adj[u]; adj[u] = e++;

}



void print_edge(int s) {

    printf("%d:", s);

    for (int e = adj[s]; ~e; e = gnxt[e])

        printf(" %d", gto[e]);

    putchar('\n');

}



int dis[maxN], pre[maxN];

int qu[maxN], qh, qt; bool inq[maxN];

void bellman_ford(int s) {

    memset(dis, 0x3f, sizeof dis); dis[s] = 0;

    for (inq[qu[qh = qt = 0] = s] = 1; qh <= qt; inq[qu[qh++ % N]] = 0)

        for (int u = qu[qh % N], e = adj[u], v = gto[e]; ~e; v = gto[e = gnxt[e]])

            if (dis[v] > dis[u] + length[e]) {

                dis[v] = dis[u] + length[e];

                pre[v] = cost[e];

                if (!inq[v]) inq[qu[++qt % N] = v] = 1;

            } else if (dis[v] == dis[u] + length[e]) {

                pre[v] = min(pre[v], cost[e]);

            }

}



int main() {

    while (~scanf("%d%d", &N, &M) && (N || M)) {

        memset(adj, -1, sizeof adj);

        for (int i = 0; i != M; ++i) {

            int u, v, d, c; scanf("%d%d%d%d", &u, &v, &d, &c);

            add_edge(u, v, d, c); add_edge(v, u, d, c);

        }

        bellman_ford(1);

        long long ans = 0;

        for (int i = 1; i <= N; ++i) ans += pre[i];

        printf("%lld\n", ans);

    }

    return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <iostream>

#include <queue>

#include <functional>

#include <cstring>

using namespace std;

#define MAX_V 10240

 

// 从?点from指向?点to的???cost的?

typedef struct edge

{

	int to, distance, cost;

	edge(){}

	edge(int to, int distance, int cost) : to(to), distance(distance), cost(cost){}

	bool operator > (const edge & b) const

	{

		return distance != b.distance  ? distance > b.distance : cost > b.cost;

	}

} P;

 

// first 最短路径，second?点?号

 

// ?

vector<edge> G[MAX_V];

 

// V是?点数

int V;

bool visited[MAX_V];

 

// 求解从?点s出?到所有点的最短花?

int dijkstra(int s)

{

	int result = 0;

	priority_queue<P, vector<P>, greater<P> > que;

	memset(visited, 0, V * sizeof(bool));

	que.push(P(0, 0, 0));

 

	while (!que.empty())

	{

		P p = que.top(); que.pop();

		int v = p.to;

		if (visited[v]) continue;

		visited[v] = true;

		result += p.cost;

		for (int i = 0; i < G[v].size(); ++i)

		{

			edge e = G[v][i];

			que.push(P(G[v][i].to, p.distance + G[v][i].distance, G[v][i].cost));

		}

	}

 

	return result;

}

 

///////////////////////////SubMain//////////////////////////////////

int main(int argc, char *argv[])

{

	int /*N = V,*/ M;

	while (cin >> V >> M && V)

	{

		for (int i = 0; i < V; ++i)

		{

			G[i].clear();

		}

		for (int i = 0; i < M; ++i)

		{

			int u, v, d, c;

			cin >> u >> v >> d >> c;

			--u, --v;

			G[u].push_back(edge(v, d, c));

			G[v].push_back(edge(u, d, c));

		}

 

		cout << dijkstra(0) << endl;

	}

	return 0;

}

// Optimized solution to the same problem (faster):
#include <cstdio>

#include <cstring>

#include <algorithm>



using namespace std;



constexpr int maxN = 10005;

constexpr int maxM = 400005;



int N, M;



int adj[maxN], gto[maxM], gnxt[maxM], length[maxM], cost[maxM], e;

void add_edge(int u, int v, int d, int c) {

    gto[e] = v; length[e] = d; cost[e] = c; gnxt[e] = adj[u]; adj[u] = e++;

}



void print_edge(int s) {

    printf("%d:", s);

    for (int e = adj[s]; ~e; e = gnxt[e])

        printf(" %d", gto[e]);

    putchar('\n');

}



int dis[maxN], pre[maxN];

int qu[maxN], qh, qt; bool inq[maxN];

void bellman_ford(int s) {

    memset(dis, 0x3f, sizeof dis); dis[s] = 0;

    for (inq[qu[qh = qt = 0] = s] = 1; qh <= qt; inq[qu[qh++ % N]] = 0)

        for (int u = qu[qh % N], e = adj[u], v = gto[e]; ~e; v = gto[e = gnxt[e]])

            if (dis[v] > dis[u] + length[e]) {

                dis[v] = dis[u] + length[e];

                pre[v] = cost[e];

                if (!inq[v]) inq[qu[++qt % N] = v] = 1;

            } else if (dis[v] == dis[u] + length[e]) {

                pre[v] = min(pre[v], cost[e]);

            }

}



int main() {

    while (~scanf("%d%d", &N, &M) && (N || M)) {

        memset(adj, -1, sizeof adj);

        for (int i = 0; i != M; ++i) {

            int u, v, d, c; scanf("%d%d%d%d", &u, &v, &d, &c);

            add_edge(u, v, d, c); add_edge(v, u, d, c);

        }

        bellman_ford(1);

        long long ans = 0;

        for (int i = 1; i <= N; ++i) ans += pre[i];

        printf("%lld\n", ans);

    }

    return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include "iostream"

#include "cstring"

#include "cstdio"

#include "queue"

using namespace std;

const int N = 10010;

const int INF = 0x3fffffff;

int pre[N];

struct Edge

{

	int x, y, d, c;

	int next;

	Edge(){}

	Edge(int X, int Y, int D, int C):x(X), y(Y), d(D), c(C){}

}p, q, e[N * 4];

int dis[N], cost[N], vis[N]; 

queue<int> que;

void spfa(int n)

{

	for(int i = 1; i <= n; ++ i){

		dis[i] = INF;

		vis[i] = 0;

	}

	dis[1] = 0;

	cost[1] = 0;

	que.push(1);

	while(!que.empty()){

		int u = que.front();

		vis[u] = 0;

		que.pop();

		for(int i = pre[u]; i != -1; i = e[i].next){

			int v = e[i].y, d = e[i].d, c = e[i].c;

			if(dis[v] > dis[u] + d || (dis[v] == dis[u] + d && cost[v] > c)){

				dis[v] = dis[u] + d;

				cost[v] = c;

				if(!vis[v]){

					vis[v] = 1;

					que.push(v);

				}

			}

		}

	}

} 

int main(void)

{

	int n, m;

	while(scanf("%d %d", &n, &m) && (n || m)){

		memset(pre, -1, sizeof(pre));

		int x, y, d, c;

		int tot = 1;

		for(int i = 1; i <= m; ++ i){

			scanf("%d %d %d %d", &x, &y, &d, &c);

			e[tot] = Edge(x, y, d, c);

			e[tot].next = pre[x];

			pre[x] = tot++;

			e[tot] = Edge(y, x, d, c);

			e[tot].next = pre[y];

			pre[y] = tot++;

		}

		spfa(n);

		int ans = 0;

		for(int i = 1; i <= n; ++ i){

			ans += cost[i];

		}

		cout << ans << endl;

	}

	return 0;

}

// Optimized solution to the same problem (faster):
#include <cstdio>

#include <cstring>

#include <algorithm>



using namespace std;



constexpr int maxN = 10005;

constexpr int maxM = 400005;



int N, M;



int adj[maxN], gto[maxM], gnxt[maxM], length[maxM], cost[maxM], e;

void add_edge(int u, int v, int d, int c) {

    gto[e] = v; length[e] = d; cost[e] = c; gnxt[e] = adj[u]; adj[u] = e++;

}



void print_edge(int s) {

    printf("%d:", s);

    for (int e = adj[s]; ~e; e = gnxt[e])

        printf(" %d", gto[e]);

    putchar('\n');

}



int dis[maxN], pre[maxN];

int qu[maxN], qh, qt; bool inq[maxN];

void bellman_ford(int s) {

    memset(dis, 0x3f, sizeof dis); dis[s] = 0;

    for (inq[qu[qh = qt = 0] = s] = 1; qh <= qt; inq[qu[qh++ % N]] = 0)

        for (int u = qu[qh % N], e = adj[u], v = gto[e]; ~e; v = gto[e = gnxt[e]])

            if (dis[v] > dis[u] + length[e]) {

                dis[v] = dis[u] + length[e];

                pre[v] = cost[e];

                if (!inq[v]) inq[qu[++qt % N] = v] = 1;

            } else if (dis[v] == dis[u] + length[e]) {

                pre[v] = min(pre[v], cost[e]);

            }

}



int main() {

    while (~scanf("%d%d", &N, &M) && (N || M)) {

        memset(adj, -1, sizeof adj);

        for (int i = 0; i != M; ++i) {

            int u, v, d, c; scanf("%d%d%d%d", &u, &v, &d, &c);

            add_edge(u, v, d, c); add_edge(v, u, d, c);

        }

        bellman_ford(1);

        long long ans = 0;

        for (int i = 1; i <= N; ++i) ans += pre[i];

        printf("%lld\n", ans);

    }

    return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<iostream>

#include<vector>

#include<queue>

#include<algorithm>

#include<cstring>

using namespace std;

const int maxn  = 1e4+10;

const int INF = 0x3f3f3f3f;

typedef pair<int,int> P;

struct edge{

	int to,dis,cost;

		

};



int d[maxn];

int value[maxn];



int N,M;



int dijkstra(vector<edge>G[])

{



	memset(d,INF,sizeof(d));

	//memset(value,INF,sizeof(value));

	priority_queue<P,vector<P>,greater<P> > que;

		

	d[1] = 0;

	value[1] = 0;

	que.push(P(d[1],1));

	

	int res = 0;

	while(!que.empty())

	{

		P p  = que.top(); que.pop();

		

		int v = p.second;

		if(d[v] < p.first)

			continue;

			

		res += value[v];

		

		for(int i = 0; i < G[v].size(); i++)

		{

			edge e = G[v][i];

			if(d[e.to] == d[v] + e.dis)

				value[e.to] = min(value[e.to],e.cost);

			if(d[e.to] > d[v] + e.dis)

			{

				d[e.to] = d[v] + e.dis;

				que.push(P(d[e.to],e.to));

				

				value[e.to] = e.cost;

			}

		}

	}

	return res;

	

}



int main()

{



	//freopen("c:\\users\\administrator\\desktop\\in.txt","r",stdin);

	while(cin >> N >> M, N||M)

	{

		

		vector<edge> G[maxn];

		for(int i =0; i < M; i++)

		{

			int u,v,d,c;

			edge e;

			cin >> u >> v >> d >> c;

			e.to= v, e.dis= d, e.cost =c;

			G[u].push_back(e);

			e.to= u;

			G[v].push_back(e);	

		}

		

		int res = dijkstra(G);

		cout << res <<endl;

	}		

} 

// Optimized solution to the same problem (faster):
#include <cstdio>

#include <cstring>

#include <algorithm>



using namespace std;



constexpr int maxN = 10005;

constexpr int maxM = 400005;



int N, M;



int adj[maxN], gto[maxM], gnxt[maxM], length[maxM], cost[maxM], e;

void add_edge(int u, int v, int d, int c) {

    gto[e] = v; length[e] = d; cost[e] = c; gnxt[e] = adj[u]; adj[u] = e++;

}



void print_edge(int s) {

    printf("%d:", s);

    for (int e = adj[s]; ~e; e = gnxt[e])

        printf(" %d", gto[e]);

    putchar('\n');

}



int dis[maxN], pre[maxN];

int qu[maxN], qh, qt; bool inq[maxN];

void bellman_ford(int s) {

    memset(dis, 0x3f, sizeof dis); dis[s] = 0;

    for (inq[qu[qh = qt = 0] = s] = 1; qh <= qt; inq[qu[qh++ % N]] = 0)

        for (int u = qu[qh % N], e = adj[u], v = gto[e]; ~e; v = gto[e = gnxt[e]])

            if (dis[v] > dis[u] + length[e]) {

                dis[v] = dis[u] + length[e];

                pre[v] = cost[e];

                if (!inq[v]) inq[qu[++qt % N] = v] = 1;

            } else if (dis[v] == dis[u] + length[e]) {

                pre[v] = min(pre[v], cost[e]);

            }

}



int main() {

    while (~scanf("%d%d", &N, &M) && (N || M)) {

        memset(adj, -1, sizeof adj);

        for (int i = 0; i != M; ++i) {

            int u, v, d, c; scanf("%d%d%d%d", &u, &v, &d, &c);

            add_edge(u, v, d, c); add_edge(v, u, d, c);

        }

        bellman_ford(1);

        long long ans = 0;

        for (int i = 1; i <= N; ++i) ans += pre[i];

        printf("%lld\n", ans);

    }

    return 0;

}

// Fastest known solution for this problem: