/* -*- coding: utf-8 -*-
 *
 * 3669.cc:  No.3669 隸ｯ蟾ｮ扈昜ｸ榊・隶ｸ - yukicoder
 */

#include<cstdio>
#include<vector>
#include<queue>
#include<algorithm>
#include<numeric>
#include<utility>

using namespace std;

/* constant */

const int MAX_N = 30000;
const int MAX_A = 300;
const int INF = MAX_N * MAX_A + 1;

/* typedef */

using ll = long long;

struct Frac {
  ll n, d;
  Frac(int _n = 0, int _d = 1): n(_n), d(_d) { __reduce(); }

  void __reduce() {
    int g = gcd(abs(n), d);
    n /= g, d /= g;
  }

  Frac operator+(const Frac &f) { return Frac(n * f.d + f.n * d, d * f.d); }
  Frac operator-() { return Frac(-n, d); }

  bool operator<(const Frac &f) const { return n * f.d < f.n * d; }
  bool operator>(const Frac &f) const { return n * f.d > f.n * d; }
  bool operator==(const Frac &f) const { return n * f.d == f.n * d; }
  bool operator!=(const Frac &f) const { return n * f.d != f.n * d; }
};

using pif = pair<int,Frac>;
using pfi = pair<Frac,int>;
using vpif = vector<pif>;

/* global variables */

vpif nbrs[MAX_N];
Frac ds[MAX_N];

/* subroutines */

/* main */

int main() {
  int n, m;
  scanf("%d%d", &n, &m);
  for (int i = 0; i < m; i++) {
    int u, v, a, b;
    scanf("%d%d%d%d", &u, &v, &a, &b);
    u--, v--;
    Frac w(a, b);
    nbrs[u].push_back({v, w});
    nbrs[v].push_back({u, w});
  }

  fill(ds, ds + n, INF);
  ds[0] = 0;

  priority_queue<pfi> q;
  q.push({0, 0});

  while (! q.empty()) {
    auto [ud, u] = q.top(); q.pop();
    ud = -ud;
    if (ds[u] != ud) continue;

    for (auto [v, w]: nbrs[u]) {
      auto vd = ud + w;
      if (ds[v] > vd) ds[v] = vd, q.push({-vd, v});
    }
  }

  for (int i = 1; i < n; i++) printf("%lld %lld\n", ds[i].n, ds[i].d);
  
  return 0;
}