#include <cmath>
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <list>
#include <time.h>
#include <math.h>
#include <random>
#include <deque>
#include <queue>
#include <cassert>
#include <unordered_map>
#include <iomanip>
#include <bitset>

using namespace std;

typedef long long ll;

mt19937 rnd(228);

struct edge
{
    int v, to, time, cost;
};

const int N = 2000 + 1;
const double inf = 1e18;

vector <edge> g[N];
int sum_a[N];
int sum_b[N];
double dist[N];
ll best[N];

int n, m;

void build_paths(double cur)
{
    for (int i = 0; i < n; i++)
    {
        dist[i] = inf;
    }
    dist[0] = 0;
    set <pair <double, int> > q;
    q.insert({0, 0});
    while (!q.empty())
    {
        int v = q.begin()->second;
        q.erase(q.begin());
        for (auto x : g[v])
        {
            if (dist[x.to] > dist[x.v] + x.time * cur + x.cost * (1 - cur))
            {
                q.erase({dist[x.to], x.v});
                sum_a[x.to] = sum_a[x.v] + x.time;
                sum_b[x.to] = sum_b[x.v] + x.cost;
                dist[x.to] = dist[x.v] + x.time * cur + x.cost * (1 - cur);
                q.insert({dist[x.to], x.to});
            }
        }
    }
    for (int i = 0; i < n; i++)
    {
        if (dist[i] <= inf / 2)
        {
            best[i] = min(best[i], sum_a[i] * (ll) sum_b[i]);
        }
    }
}

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++)
    {
        best[i] = 1e18;
    }
    vector <edge> e;
    for (int i = 0; i < m; i++)
    {
        int u, v, time, cost;
        scanf("%d%d%d%d", &u, &v, &time, &cost);
        u--, v--;
        e.push_back({u, v, time, cost});
        e.push_back({v, u, time, cost});
        g[u].push_back({u, v, time, cost});
        g[v].push_back({v, u, time, cost});
    }
    double x = 0;
    while (true)
    {
        double new_x = 1;
        build_paths(x);
        for (auto c : e)
        {
            int v = c.v, to = c.to, time = c.time, cost = c.cost;
            if (best[v] == 1e18)
            {
                continue;
            }
            int new_path_a = sum_a[v] + time;
            int new_path_b = sum_b[v] + cost;
            int cur_path_a = sum_a[to];
            int cur_path_b = sum_b[to];
            new_path_a -= new_path_b;
            cur_path_a -= cur_path_b;
            double pos = (cur_path_b - new_path_b) / (double) (new_path_a - cur_path_a);
            if (x < pos && pos <= new_x)
            {
                new_x = pos;
            }
        }
        if (x == new_x)
        {
            break;
        }
        x = new_x;
    }
    for (int i = 1; i < n; i++)
    {
        if (best[i] == 1e18)
        {
            best[i] = -1;
        }
        printf("%lld\n", best[i]);
    }
}