#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
using namespace std;

const int INF = 0x3f3f3f3f;
const int MAXN = 10000;
const int MAXM = 20000;
struct Edge {
    int to, next;
    int c, d;
}edge[MAXM * 2];
int n, m;
int head[MAXN], L;

void addEdge(int u, int v, int d, int c) {
    edge[L].to = v;
    edge[L].d = d;
    edge[L].c = c;
    edge[L].next = head[u];
    head[u] = L++;
}

bool inq[MAXN];
int dis[MAXN];
void SPFA() {
    queue<int> Q;
    for (int i = 0; i < n; i++) {
        inq[i] = false;
        dis[i] = INF;
    }
    Q.push(0);
    dis[0] = 0;
    while (!Q.empty()) {
        int now = Q.front();
        Q.pop();
        inq[now] = false;
        for (int i = head[now]; i != -1; i = edge[i].next) {
            int v = edge[i].to;
            if (dis[v] > dis[now] + edge[i].d) {
                dis[v] = dis[now] + edge[i].d;
                if (inq[v] == false) {
                    inq[v] = true;
                    Q.push(v);
                }
            }
        }
    }
}

struct Fuck {
    int u, v, cost;
    Fuck(){}
    Fuck(int _u, int _v, int _c) {
        u = _u;
        v = _v;
        cost = _c;
    }
}fuck[MAXM * 2];
int tot;
int pre[MAXN], id[MAXN], visit[MAXN], in[MAXN];

int zhuliu(int root, int n, int m, Fuck e[]) {
    int res = 0, u, v;
    while (true) {
        for (int i = 0; i < n; i++)
            in[i] = INF;
        for (int i = 0; i < m; i++)
            if (e[i].u != e[i].v && e[i].cost < in[e[i].v]) {
                pre[e[i].v] = e[i].u;
                in[e[i].v] = e[i].cost;
            }
        for (int i = 0; i < n; i++)
            if (i != root)
                if (in[i] == INF)   return -1;
        int tn = 0;
        memset(id, -1, sizeof(id));
        memset(visit, -1, sizeof(visit));
        in[root] = 0;
        for (int i = 0; i < n; i++) {
            res += in[i];
            v = i;
            while (visit[v] != i && id[v] == -1 && v != root) {
                visit[v] = i;
                v = pre[v];
            }
            if (v != root && id[v] == -1) {
                for (int u = pre[v]; u != v; u = pre[u])
                    id[u] = tn;
                id[v] = tn++;
            }
        }
        if (tn == 0)    break;
        for (int i = 0; i < n; i++)
            if (id[i] == -1)
                id[i] = tn++;
        for (int i = 0; i < m;) {
            int v = e[i].v;
            e[i].u = id[e[i].u];
            e[i].v = id[e[i].v];
            if (e[i].u != e[i].v)
                e[i++].cost -= in[v];
            else
                swap(e[i], e[--m]);
        }
        n = tn;
        root = id[root];
    }
    return res;
}

int solve() {
    tot = 0;
    for (int u = 0; u < n; u++)
        for (int i = head[u]; i != -1; i = edge[i].next) {
            int v = edge[i].to;
            if (dis[v] == dis[u] + edge[i].d)
                fuck[tot++] = Fuck(u, v, edge[i].c);
        }
    return zhuliu(0, n, tot, fuck);
}

int main() {
	while (true) {
	    scanf("%d%d", &n, &m);
	    if (n == 0 && m == 0)   break;
        for (int i = 0; i < n; i++)
            head[i] = -1;
        L = 0;
        for (int i = 0; i < m; i++) {
            int u, v, c, d;
            scanf("%d%d%d%d", &u, &v, &d, &c);
            u--;
            v--;
            addEdge(u, v, d, c);
            addEdge(v, u, d, c);
        }
        SPFA();
        printf("%d\n", solve());
	}
    return 0;
}

Measured memory_bytes: 2216