use std::{cmp::Reverse, collections::BinaryHeap};

use num::{BigInt, BigRational, Zero};
use proconio::{fastout, input, marker::Usize1};

#[fastout]
fn main() {
    input! {
        n: usize, m: usize,
        edges: [(Usize1, Usize1, u32, u32); m],
    }

    let mut graph = vec![vec![]; n];
    for &(u, v, a, b) in &edges {
        let a = BigInt::zero() + a;
        let b = BigInt::zero() + b;
        let r = BigRational::new(a, b);
        graph[u].push((v, r.clone()));
        graph[v].push((u, r));
    }

    let mut heap = BinaryHeap::new();
    let mut dist = vec![None; n];
    heap.push((Reverse(BigRational::zero()), 0));
    dist[0] = Some(BigRational::zero());

    while let Some((Reverse(d), v)) = heap.pop() {
        if dist[v].as_ref().is_some_and(|d_v| d_v != &d) {
            continue;
        }

        for &(u, ref w) in &graph[v] {
            let nd = &d + w;
            if dist[u].as_ref().is_none_or(|d_u| d_u > &nd) {
                dist[u] = Some(nd.clone());
                heap.push((Reverse(nd), u));
            }
        }
    }

    for r in &dist[1..] {
        let r = r.as_ref().unwrap();
        println!("{} {}", r.numer(), r.denom());
    }
}