#include <iostream>
#include <cstring>
#include <cstdio>
#include <queue>
#include <vector>
#include <algorithm>

using namespace std;

const int N=10006, INF=0x3fffffff;

int dis[N];
bool vs[N], n, m;
struct data {
    int u, dis, cost;
    data() {}
    data(int _u, int _dis, int _cost) : u(_u), dis(_dis), cost(_cost) {}
};
vector <data> arc[N];
queue <int> Q;

struct ARC {
    int s, t, val;
    ARC() {}
    ARC(int _s, int _t, int _val) : s(_s), t(_t), val(_val) {}
    bool operator <(const ARC &T) const {
        return val<T.val;
    }
};
vector <ARC> hehe;

void BFS() {
    while(!Q.empty()) Q.pop();
    for(int i=1; i<=n; i++) dis[i]=INF;
    memset(vs, 0, sizeof vs);
    vs[1]=1, Q.push(1), dis[1]=0;
    while(!Q.empty()) {
        int cur=Q.front();
        Q.pop(), vs[cur]=0;
        int len=(int)arc[cur].size();
        for(int i=0; i<len; i++) {
            int u=arc[cur][i].u;
            int DIS=arc[cur][i].dis;
            if(dis[u]>dis[cur]+DIS) {
                dis[u]=dis[cur]+DIS;
                if(!vs[u]) vs[u]=1, Q.push(u);
            }
        }
    }
}

void update(int id) {
    int len=(int)arc[id].size();
    for(int i=0; i<len; i++) {
        int u=arc[id][i].u;
        int DIS=arc[id][i].dis;
        int COST=arc[id][i].cost;
        if(dis[id]+DIS!=dis[u] || vs[u]) continue;
        hehe.push_back(ARC(id, u, COST));
    }
}

int main() {
    freopen("/home/lovezzt/桌面/in.txt", "r", stdin);
    while(scanf("%d%d", &n, &m), n!=0 || m!=0) {
        for(int i=1; i<=n; i++) arc[i].clear();
        for(int i=0, a, b, c, d; i<m; i++) {
            scanf("%d%d%d%d", &a, &b, &c, &d);
            arc[a].push_back(data(b, c, d));
            arc[b].push_back(data(a, c, d));
        }
        BFS();
        memset(vs, 0, sizeof vs);
        int sum=0, tot=1;
        vs[1]=1;
        update(1);
        hehe.clear();
        while(tot<n) {
            int len=(int)hehe.size();
            int Min=INF, id;
            for(int i=0; i<len; i++) {
                int t=hehe[i].t;
                int 
            }
        }
    }
    return 0;
}