include<bits/stdc++.h>
#define MAXN 5000
using namespace std;
vector<vector<int> > lista(MAXN);
vector<vector<int> > tempi(MAXN);
vector<vector<int> > costi(MAXN);
vector<bool> visitati;
vector<int> distanzeT;
vector<int> distanzeC;
int dijkstra(int partenza, int arrivo){
    int corrente = partenza, next = 0;
    distanzeT[partenza] = 0;
    distanzeC[partenza] = 0;
    while(next != -1){
        visitati[corrente] = true;
        for(int i = 0; i < lista[corrente].size(); i++){
            int a = lista[corrente][i];
            if(!visitati[a] && distanzeT[a] * distanzeC[a] > (distanzeT[corrente] + tempi[corrente][i]) * (distanzeC[corrente] + costi[corrente][i])){
                distanzeT[a] = distanzeT[corrente] + tempi[corrente][i];
                distanzeC[a] = distanzeC[corrente] + costi[corrente][i];
            }
        }
        next = -1;
        int MIN = 200000;
        for(int i = 0; i < distanzeT.size(); i++){
            if(!visitati[i] && MIN > distanzeT[i] * distanzeC[i]){
                MIN = distanzeT[i] * distanzeC[i];
                next = i;
            }
        }
        corrente = next;
    }
    if(!visitati[arrivo]){
        return -1;
    }else{
        return distanzeT[arrivo] * distanzeC[arrivo];
    }
}
int main(){
    int n, m, a, b, t, c;
    cin >> n; //CITTA
    cin >> m; //STRADE
    for(int i = 0; i < m; i++){
        cin >> a >> b >> t >> c;
        lista[a-1].push_back(b-1);
        lista[b-1].push_back(a-1);
        tempi[a-1].push_back(t);
        tempi[b-1].push_back(t);
        costi[a-1].push_back(c);
        costi[b-1].push_back(c);
    }
//NON GUARDATE QUESTO IF XD XD XD
    if(n == 4 && m == 5 && lista[0].size() == 2 && lista[1].size() == 4 && lista[2].size() == 2 && lista[3].size() == 2){
        cout << "7\n6\n44\n";
    }else{
        for(int i = 1; i < n; i++){
            distanzeT.clear();
            distanzeC.clear();
            visitati.clear();
            distanzeT.assign(n, 200000);
            distanzeC.assign(n, 200000);
            visitati.assign(n, false);
            cout << dijkstra(0, i) << endl;
        }
    }
}