pub trait Zero {
    fn zero() -> Self;
}

impl Zero for usize { fn zero() -> Self { 0 } }
impl Zero for u64 { fn zero() -> Self { 0 } }
impl Zero for u32 { fn zero() -> Self { 0 } }
impl Zero for u16 { fn zero() -> Self { 0 } }
impl Zero for u8 { fn zero() -> Self { 0 } }
impl Zero for isize { fn zero() -> Self { 0 } }
impl Zero for i64 { fn zero() -> Self { 0 } }
impl Zero for i32 { fn zero() -> Self { 0 } }
impl Zero for i16 { fn zero() -> Self { 0 } }
impl Zero for i8 { fn zero() -> Self { 0 } }

pub trait IsNN {}

impl IsNN for usize {}
impl IsNN for u64 {}
impl IsNN for u32 {}
impl IsNN for u16 {}
impl IsNN for u8 {}

pub trait IsNum: ToNNeg + ToArb { }
impl<N: ToNNeg + ToArb> IsNum for N { }

pub trait ToNNeg {
    type Output: Zero + IsNum + IsNN + std::ops::Add<Output=Self::Output> + std::ops::Sub<Output=Self::Output> + std::cmp::Ord + Copy;
    fn to_nneg(&self) -> Self::Output;
}

impl ToNNeg for usize {
    type Output = usize;
    fn to_nneg(&self) -> Self::Output { self.clone() }
}

impl ToNNeg for u64 {
    type Output = u64;
    fn to_nneg(&self) -> Self::Output { self.clone() }
}

impl ToNNeg for u32 {
    type Output = u32;
    fn to_nneg(&self) -> Self::Output { self.clone() }
}

impl ToNNeg for u16 {
    type Output = u16;
    fn to_nneg(&self) -> Self::Output { self.clone() }
}

impl ToNNeg for u8 {
    type Output = u8;
    fn to_nneg(&self) -> Self::Output { self.clone() }
}

impl ToNNeg for isize {
    type Output = usize;
    fn to_nneg(&self) -> Self::Output {
        match self.clone() {
            num if num >= 0 => num as Self::Output,
            _ => unreachable!()
        }
    }
}

impl ToNNeg for i64 {
    type Output = u64;
    fn to_nneg(&self) -> Self::Output {
        match self.clone() {
            num if num >= 0 => num as Self::Output,
            _ => unreachable!()
        }
    }
}

impl ToNNeg for i32 {
    type Output = u32;
    fn to_nneg(&self) -> Self::Output {
        match self.clone() {
            num if num >= 0 => num as Self::Output,
            _ => unreachable!()
        }
    }
}
impl ToNNeg for i16 {
    type Output = u16;
    fn to_nneg(&self) -> Self::Output {
        match self.clone() {
            num if num >= 0 => num as Self::Output,
            _ => unreachable!()
        }
    }
}

impl ToNNeg for i8 {
    type Output = u8;
    fn to_nneg(&self) -> Self::Output {
        match self.clone() {
            num if num >= 0 => num as Self::Output,
            _ => unreachable!()
        }
    }
}

pub trait ToArb {
    type Output: Zero + IsNum + std::ops::Add<Output=Self::Output> + std::ops::Sub<Output=Self::Output> + std::cmp::Ord + Copy;
    fn to_arb(&self) -> Self::Output;
}

impl ToArb for isize {
    type Output = isize;
    fn to_arb(&self) -> Self::Output { self.clone() }
}

impl ToArb for i64 {
    type Output = i64;
    fn to_arb(&self) -> Self::Output { self.clone() }
}

impl ToArb for i32 {
    type Output = i32;
    fn to_arb(&self) -> Self::Output { self.clone() }
}

impl ToArb for i16 {
    type Output = i16;
    fn to_arb(&self) -> Self::Output { self.clone() }
}

impl ToArb for i8 {
    type Output = i8;
    fn to_arb(&self) -> Self::Output { self.clone() }
}

impl ToArb for usize {
    type Output = isize;
    fn to_arb(&self) -> Self::Output {
        self.clone() as isize
    }
}

impl ToArb for u64 {
    type Output = i64;
    fn to_arb(&self) -> Self::Output {
        self.clone() as i64
    }
}

impl ToArb for u32 {
    type Output = i32;
    fn to_arb(&self) -> Self::Output {
        self.clone() as i32
    }
}

impl ToArb for u16 {
    type Output = i16;
    fn to_arb(&self) -> Self::Output {
        self.clone() as i16
    }
}

impl ToArb for u8 {
    type Output = i8;
    fn to_arb(&self) -> Self::Output {
        self.clone() as i8
    }
}

pub trait Integer: Sized + std::ops::Shl<usize, Output=Self> + std::ops::Shr<usize, Output=Self> {}

impl Integer for usize {}
impl Integer for u64 {}
impl Integer for u32 {}
impl Integer for u16 {}
impl Integer for u8 {}
impl Integer for isize {}
impl Integer for i64 {}
impl Integer for i32 {}
impl Integer for i16 {}
impl Integer for i8 {}

/// Trait for properties.
pub trait Property: Copy {}

impl<P> Property for P where P: Copy {}

/// Types implementing `ToNNegWeight` are able to convert to non-negative weights.
/// This trait use the algorithms with potentials (`dijkstra_with_potential`, etc...).
pub trait ToNNegWeight {

    /// converting type.
    type Output: NNegWeight;

    /// convert to non-negative weights.
    fn to_nnegw(&self) -> Self::Output;
}

/// Types implementing `ToARbWeight` are able to convert to arbitrary weights.
/// This trait use to reverse from non-negative weight after converting weight.
pub trait ToArbWeight {

    /// converting type.
    type Output: ArbWeight;

    /// convert to non-negative weights.
    fn to_arbw(&self) -> Self::Output;
}

/// Trait of arbitrary weights.
/// the arbirary weight has infinity, zero and negative infinity.
pub trait ArbWeight where Self: ToNNegWeight + ToArbWeight + Property + std::ops::Add<Output=Self> + std::cmp::Ord {
    fn inf() -> Self;
    fn zero() -> Self;
    fn neg_inf() -> Self { unreachable!() }
}

/// Trait of non-negative weights.
pub trait NNegWeight where Self: ArbWeight {}

/// Trait of weights of integer. 
/// types implementing this use the scaling algorithms.
pub trait IntegerWeight: ArbWeight + std::ops::Shl<usize, Output=Self> + std::ops::Shr<usize, Output=Self> {}

impl<W> IntegerWeight for W where W: ArbWeight + std::ops::Shl<usize, Output=Self> + std::ops::Shr<usize, Output=Self> {}

pub trait SubtractableWeight: ArbWeight + std::ops::Sub<Output=Self> {}

impl<W> SubtractableWeight for W where W: ArbWeight + std::ops::Sub<Output=Self> {}

/// Trait of capacity for maxflow, mcf, and so on.
pub trait Capacity: ArbWeight + IntegerWeight + SubtractableWeight  {}

impl<W> Capacity for W where W: ArbWeight + IntegerWeight + SubtractableWeight {}

pub trait Cost<Cap>: ArbWeight + SubtractableWeight + std::ops::Mul<Cap, Output=Self> {}

impl<Co, Cap> Cost<Cap> for Co where Cap: Capacity, Co: ArbWeight + SubtractableWeight + SubtractableWeight + std::ops::Mul<Cap, Output=Self> {}

/// Trait for elements of graph (Vertex, Edge, ...) that have ID (usize).
/// the elements implementing ID are able to use [`graph::kernel::Properties`].
pub trait ID {

    /// return id of the element.
    fn id(&self) -> usize;
}

/// Implementing ID for usize.
impl ID for usize {

    /// return the own value
    fn id(&self) -> usize { *self }
}

/// Trait for vertices of graphs.
pub trait Vertex: ID + Eq + Copy { }

impl<V: ID + Eq + Copy> Vertex for V { }

/// Trait for edges of graphs. 
pub trait Edge {

    /// Vertex type at both ends of edge
    type VType: Vertex;

    /// Start point of edge
    fn from(&self) -> &Self::VType;

    /// End point of edge
    fn to(&self) -> &Self::VType;
}

/// Implementing Edge for the simple tuple. 
impl<V> Edge for (V, V) where V: Vertex { 
    type VType = V;
    fn from(&self) -> &Self::VType { &self.0 }
    fn to(&self) -> &Self::VType { &self.1 }
}

/// Implementing Edge for the simple tuple. 
impl<V, P> Edge for (V, V, P) where V: Vertex, P: Property { 
    type VType = V;
    fn from(&self) -> &Self::VType { &self.0 }
    fn to(&self) -> &Self::VType { &self.1 }
}

/// Trait for adjacency edges of graph.
/// Why do we use [`Edge`] as is? There are 2 reasons.
/// - To give values to the edges to use Properties (AdjEdge has ID).
/// - When using a undirected graph as a directed graph, must swap two ends of edge.
pub trait AdjEdge: ID + Edge {

    /// Edge type of raw edge.
    type EType: Edge<VType=Self::VType>;

    /// return raw edge.
    fn edge(&self) -> &Self::EType;
}

/// Trait for adjcency edges on ResidualNetwork.
/// It has reverse edge.
pub trait ResidualEdge: AdjEdge {
    fn rev(&self) -> Self;
}

/// Trait of graph.
pub trait Graph<'a> {
    /// Type of vertices.
    type VType: Vertex + 'a;

    /// Type of edges.
    type EType: Edge<VType=Self::VType>;

    /// Type of adjacency edges.
    type AEType: AdjEdge<VType=Self::VType, EType=Self::EType>;

    /// Type of iterator for adjacency list.
    type AdjIter: std::iter::Iterator<Item=Self::AEType>;

    /// Type of iterator for edges list.
    type EIter: std::iter::Iterator<Item=Self::AEType>;

    /// Type of iterator for vertices list.
    type VIter: std::iter::Iterator<Item=&'a Self::VType>;

    /// return adjacency list from the vertex v.
    fn delta(&'a self, v: &Self::VType) -> Self::AdjIter;

    /// return edges list.
    fn edges(&'a self) -> Self::EIter;

    /// return vertices list.
    fn vertices(&'a self) -> Self::VIter;

    /// return the number of vertices.
    fn v_size(&self) -> usize;

    /// return the number of edges.
    fn e_size(&self) -> usize;
}

/// Trait of directed graph.
pub trait Directed<'a>: Graph<'a> {}

/// Trait of undirected graph.
/// graphs implementing this hold that the edge `(v, u)` exists for the edge `(u, v)` when the graph
/// use as directed graph
pub trait Undirected<'a>: Graph<'a> {}

/// Trait of bipartite graph.
pub trait Bipartite<'a>: Undirected<'a> {

    /// Type of iterator for vertices in one side.
    type BVIter: std::iter::Iterator<Item=&'a Self::VType>;

    /// return vertices list in left side.
    fn left_vertices(&'a self) -> Self::BVIter;

    /// return vertices list in right side.
    fn right_vertices(&'a self) -> Self::BVIter;
}

/// Trait of residual network
/// `AEType` must be `ResidualEdge`.
pub trait Residual<'a>: Directed<'a> where <Self as Graph<'a>>::AEType: ResidualEdge {}

pub fn generate_func<AE, P, F>(f: F) -> impl Fn(&AE) -> P
where AE: AdjEdge, P: Property, F: Fn(&AE::EType) -> P {
    move |ae| f(ae.edge())
}

use std::ops::{ Index, IndexMut };

#[derive(Clone)]
pub struct Properties<W: Clone> {
    vec: Vec<W>
}

impl<'a, I: ID, W: Clone> Index<&'a I> for Properties<W> {
    type Output = W;
    fn index(&self, idx: &'a I) -> & Self::Output { &self.vec[idx.id()] }
}

impl<'a, I: ID, W: Clone> IndexMut<&'a I> for Properties<W> {
    fn index_mut(&mut self, idx: &'a I) -> &mut Self::Output { &mut self.vec[idx.id()] }
}

impl<'a, W: Clone> Properties<W> {
    pub fn new(n: usize, init: &W) -> Self {
        Properties {
           vec: vec![init.clone(); n], 
        }
    }
    pub fn iter(&'a self) -> std::slice::Iter<'a, W> { self.vec.iter() }
}

#[derive(Clone, Copy, PartialEq, Eq)]
pub enum ArbW<W> where W: Zero + IsNum + std::ops::Add<Output=W> + std::cmp::Ord + Copy {
    Inf, 
    Some(W),
    NegInf,
}

impl<W> std::ops::Add for ArbW<W> where W: Zero + IsNum + std::ops::Add<Output=W> + std::cmp::Ord + Copy {
    type Output = Self;
    fn add(self, rhs: Self) -> Self {
        match self {
            ArbW::Inf => {
                match rhs {
                    ArbW::NegInf => unreachable!(),
                    _ => ArbW::Inf,
                }
            }
            ArbW::Some(d) => {
                match rhs {
                    ArbW::Inf => ArbW::Inf,
                    ArbW::Some(d2) => ArbW::Some(d + d2),
                    ArbW::NegInf => ArbW::NegInf,
                }
            }
            ArbW::NegInf => {
                match rhs {
                    ArbW::Inf => unreachable!(),
                    _ => ArbW::NegInf,
                }
            }
        }
    }

}

impl<W> std::ops::Sub for ArbW<W> where W: Zero + IsNum + std::ops::Add<Output=W> + std::ops::Sub<Output=W> + std::cmp::Ord + Copy {
    type Output = Self;
    fn sub(self, rhs: Self) -> Self {
        match self {
            ArbW::Inf => {
                match rhs {
                    ArbW::Inf => unreachable!(),
                    _ => ArbW::Inf,
                }
            }
            ArbW::Some(d) => {
                match rhs {
                    ArbW::Inf => ArbW::NegInf,
                    ArbW::Some(d2) => ArbW::Some(d - d2),
                    ArbW::NegInf => ArbW::Inf,
                }
            }
            ArbW::NegInf => {
                match rhs {
                    ArbW::NegInf => unreachable!(),
                    _ => ArbW::NegInf,
                }
            }
        }
    }
}

impl<W,X> std::ops::Mul<ArbW<X>> for ArbW<W> 
where W: Zero + IsNum + std::ops::Add<Output=W> + std::cmp::Ord + Copy + std::ops::Mul<Output=W>,
      X: Zero + IsNum + std::ops::Add<Output=X> + std::cmp::Ord + Copy + Into<W> {
    type Output = Self;
    fn mul(self, rhs: ArbW<X>) -> Self {
        match self {
            ArbW::Inf => {
                match rhs {
                    ArbW::NegInf => ArbW::NegInf,
                    _ => ArbW::Inf,
                }
            }
            ArbW::Some(d) => {
                match rhs {
                    ArbW::Inf => ArbW::Inf,
                    ArbW::Some(d2) => ArbW::Some(d.mul(d2.into())),
                    ArbW::NegInf => ArbW::NegInf,
                }
            }
            ArbW::NegInf => {
                match rhs {
                    ArbW::NegInf => ArbW::Inf,
                    _ => ArbW::NegInf,
                }
            }
        }
    }
}

impl<W,X> std::ops::Mul<NNegW<X>> for ArbW<W> 
where W: Zero + IsNum + std::ops::Add<Output=W> + std::cmp::Ord + Copy + std::ops::Mul<Output=W>,
      X: Zero + IsNum + IsNN + std::ops::Add<Output=X> + std::cmp::Ord + Copy + Into<W> {
    type Output = Self;
    fn mul(self, rhs: NNegW<X>) -> Self {
        match self {
            ArbW::Inf => {
                ArbW::Inf
            }
            ArbW::Some(d) => {
                match rhs {
                    NNegW::Inf => ArbW::Inf,
                    NNegW::Some(d2) => ArbW::Some(d.mul(d2.into())),
                }
            }
            ArbW::NegInf => {
                ArbW::NegInf
            }
        }
    }
}


impl<W> std::cmp::PartialOrd for ArbW<W> where W: Zero + IsNum + std::ops::Add<Output=W> + std::cmp::Ord + Copy {
    fn partial_cmp(&self, rhs: &Self) -> Option<std::cmp::Ordering> {
        Some(self.cmp(rhs))
    }
}

impl<W> std::cmp::Ord for ArbW<W> where W: Zero + IsNum + std::ops::Add<Output=W> + std::cmp::Ord + Copy {
    fn cmp(&self, rhs: &Self) -> std::cmp::Ordering {
        match self {
            ArbW::Inf => {
                match rhs {
                    ArbW::Inf => std::cmp::Ordering::Equal,
                    _ => std::cmp::Ordering::Greater,
                }
            }
            ArbW::Some(d) => {
                match rhs {
                    ArbW::Inf => std::cmp::Ordering::Less,
                    ArbW::Some(d2) => d.cmp(d2), 
                    ArbW::NegInf => std::cmp::Ordering::Greater,
                }
            }
            ArbW::NegInf => {
                match rhs {
                    ArbW::NegInf => std::cmp::Ordering::Equal,
                    _ => std::cmp::Ordering::Less, 
                }
            }
        }
    }
}

impl<W> ToNNegWeight for ArbW<W> where W: Zero + IsNum + std::ops::Add<Output=W> + std::cmp::Ord + Copy {
    type Output = NNegW<<W as ToNNeg>::Output>;
    fn to_nnegw(&self) -> Self::Output {
        match self {
            ArbW::Inf => NNegW::Inf,
            ArbW::Some(ref num) => NNegW::Some(num.to_nneg()),
            ArbW::NegInf => unreachable!(), 
        }
    }
}

impl<W> ToArbWeight for ArbW<W> where W: Zero + IsNum + std::ops::Add<Output=W> + std::cmp::Ord + Copy {
    type Output = Self;
    fn to_arbw(&self) -> Self::Output {
        self.clone()
    }
}

impl<W> std::ops::Shl<usize> for ArbW<W>
where W: Zero + IsNum + Integer + std::ops::Add<Output=W> + std::cmp::Ord + Copy {
    type Output = Self;
    fn shl(self, rhs: usize) -> Self {
        match self {
            ArbW::Some(d) => ArbW::Some(d.shl(rhs)), 
            inf => inf, 
        }
    }
}

impl<W> std::ops::Shr<usize> for ArbW<W> 
where W: Zero + IsNum + Integer + std::ops::Add<Output=W> + std::cmp::Ord + Copy + std::ops::Shr<usize, Output=W> {
    type Output = Self;
    fn shr(self, rhs: usize) -> Self {
        match self {
            ArbW::Some(d) => ArbW::Some(d.shr(rhs)),
            inf => inf,
        }
    }
}


impl<W> ArbWeight for ArbW<W> where W: Zero + IsNum + std::ops::Add<Output=W> + std::cmp::Ord + Copy {
    fn inf() -> Self { ArbW::Inf }
    fn zero() -> Self { ArbW::Some(W::zero()) }
    fn neg_inf() -> Self { ArbW::NegInf }
}

#[derive(Clone, Copy, PartialEq, Eq)]
pub enum NNegW<W> where W: Zero + IsNum + IsNN + std::ops::Add<Output=W> + std::cmp::Ord + Copy {
    Inf,
    Some(W), 
}

impl<W> std::ops::Add for NNegW<W> where W: Zero + IsNum + IsNN + std::ops::Add<Output=W> + std::cmp::Ord + Copy {
    type Output = Self;
    fn add(self, rhs: Self) -> Self {
        match self {
            NNegW::Inf => {
                NNegW::Inf
            }
            NNegW::Some(d) => {
                match rhs {
                    NNegW::Inf => NNegW::Inf,
                    NNegW::Some(d2) => NNegW::Some(d + d2),
                }
            }
        }
    }

}

impl<W> std::ops::Sub for NNegW<W> where W: Zero + IsNum + IsNN + std::ops::Add<Output=W> + std::ops::Sub<Output=W> + std::cmp::Ord + Copy {
    type Output = Self;
    fn sub(self, rhs: Self) -> Self {
        match self {
            NNegW::Inf => {
                match rhs {
                    NNegW::Inf => unreachable!(),
                    _ => NNegW::Inf,
                }
            }
            NNegW::Some(d) => {
                match rhs {
                    NNegW::Inf => unreachable!(), 
                    NNegW::Some(d2) => NNegW::Some(d - d2),
                }
            }
        }
    }
}


impl<W> std::cmp::PartialOrd for NNegW<W> where W: Zero + IsNum + IsNN + std::ops::Add<Output=W> + std::cmp::Ord + Copy {
    fn partial_cmp(&self, rhs: &Self) -> Option<std::cmp::Ordering> {
        Some(self.cmp(rhs))
    }
}

impl<W> std::cmp::Ord for NNegW<W> where W: Zero + IsNum + IsNN + std::ops::Add<Output=W> + std::cmp::Ord + Copy {
    fn cmp(&self, rhs: &Self) -> std::cmp::Ordering {
        match self {
            NNegW::Inf => {
                match rhs {
                    NNegW::Inf => std::cmp::Ordering::Equal, 
                    _ => std::cmp::Ordering::Greater,
                }
            }
            NNegW::Some(d) => {
                match rhs {
                    NNegW::Inf => std::cmp::Ordering::Less,
                    NNegW::Some(d2) => d.cmp(d2), 
                }
            }
        }
    }
}

impl<W> IsNN for NNegW<W> where W: Zero + IsNum + IsNN + std::ops::Add<Output=W> + std::cmp::Ord + Copy {}

impl<W> ToNNegWeight for NNegW<W> where W: Zero + IsNum + IsNN + std::ops::Add<Output=W> + std::cmp::Ord + Copy {
    type Output = Self;
    fn to_nnegw(&self) -> Self::Output {
        self.clone()
    }
}

impl<W> ToArbWeight for NNegW<W> where W: Zero + IsNum + IsNN + std::ops::Add<Output=W> + std::cmp::Ord + Copy {
    type Output = ArbW<<W as ToArb>::Output>;
    fn to_arbw(&self) -> Self::Output {
        match self {
            NNegW::Inf => ArbW::Inf,
            NNegW::Some(ref num) => ArbW::Some(num.to_arb())
        }
    }
}

impl<W> std::ops::Shl<usize> for NNegW<W>
where W: Zero + IsNum + IsNN + Integer + std::ops::Add<Output=W> + std::cmp::Ord + Copy {
    type Output = Self;
    fn shl(self, rhs: usize) -> Self {
        match self {
            NNegW::Some(d) => NNegW::Some(d.shl(rhs)), 
            other => other, 
        }
    }
}


impl<W> std::ops::Shr<usize> for NNegW<W>
where W: Zero + IsNum + IsNN + Integer + std::ops::Add<Output=W> + std::cmp::Ord + Copy {
    type Output = Self;
    fn shr(self, rhs: usize) -> Self {
        match self {
            NNegW::Some(d) => NNegW::Some(d.shr(rhs)), 
            other => other, 
        }
    }
}

impl<W> ArbWeight for NNegW<W> where W: Zero + IsNum + IsNN + std::ops::Add<Output=W> + std::cmp::Ord + Copy {
    fn inf() -> Self { NNegW::Inf }
    fn zero() -> Self { NNegW::Some(W::zero()) }
}

impl<W> NNegWeight for NNegW<W> where W: Zero + IsNum + IsNN + std::ops::Add<Output=W> + std::cmp::Ord + Copy {}

#[derive(Clone,Copy,Eq,PartialEq,Debug)]
pub struct Eite(pub usize);

pub struct DiAdjEdge<'a, E: Edge + 'a>(&'a E, usize);

impl<'a, E: Edge + 'a> ID for DiAdjEdge<'a, E> {
    fn id(&self) -> usize { self.1 }
}

impl<'a, E> Edge for DiAdjEdge<'a, E> where E: Edge + 'a {
    type VType = E::VType;
    fn from(&self) -> &E::VType { self.0.from() }
    fn to(&self) -> &E::VType { self.0.to() }
}

impl<'a, E> AdjEdge for DiAdjEdge<'a, E> where E: Edge + 'a {
    type EType = E;
    fn edge(&self) -> &E { self.0 }
}

pub struct AdjIter<'a, E: Edge + 'a> {
    iter: std::slice::Iter<'a, Eite>,
    edges: &'a Vec<E>,
}

impl<'a, E: Edge + 'a> std::iter::Iterator for AdjIter<'a, E> {
    type Item = DiAdjEdge<'a, E>;
    fn next(&mut self) -> Option<Self::Item> {
        match self.iter.next() {
            Some(ei) => {
                Some( DiAdjEdge(&self.edges[ei.0], ei.0) )
            }
            None => {
                None
            }
        }
    }
}

pub struct EIter<'a, E: Edge + 'a> {
    i: usize,
    iter: std::slice::Iter<'a, E>,
}

impl<'a, E: Edge + 'a> std::iter::Iterator for EIter<'a, E> {
    type Item = DiAdjEdge<'a, E>;
    fn next(&mut self) -> Option<Self::Item> {
        match self.iter.next() {
            Some(e) => {
                let i = self.i;
                self.i += 1;
                Some(DiAdjEdge(&e, i))
            }
            None => None
        }
    }
}

pub struct VIter<'a, V: Vertex + 'a> {
    iter: std::slice:: Iter<'a, Option<V>>,
}

impl<'a, V: Vertex + 'a> std::iter::Iterator for VIter<'a, V> {
    type Item = &'a V;
    fn next(&mut self) -> Option<Self::Item> {
        while let Some(v) = self.iter.next() {
            if v.is_none() { continue; }
            else { return v.as_ref() }
        }
        None
    }
}

pub struct DirectedGraph<V: Vertex, E: Edge<VType=V>> {
    n: usize,
    m: usize,
    g: Vec<Vec<Eite>>,
    es: Vec<E>,
    vs: Vec<Option<V>>, 
}

impl<'a, V, E> Graph<'a> for DirectedGraph<V,E> where V: Vertex + 'a, E: Edge<VType=V> + 'a {
    type VType = V;
    type EType = E;
    type AEType = DiAdjEdge<'a, E>;
    type AdjIter = AdjIter<'a, E>;
    type EIter = EIter<'a, E>;
    type VIter = VIter<'a, V>;
    fn delta(&'a self, v: &V) -> Self::AdjIter {
        AdjIter { iter: self.g[v.id()].iter(), edges: &self.es }
    }
    fn edges(&'a self) -> Self::EIter {
        EIter { i: 0, iter: self.es.iter() }
    }
    fn vertices(&'a self) -> Self::VIter { 
        VIter { iter: self.vs.iter() }
    }
    fn v_size(&self) -> usize {
        self.n
    }
    fn e_size(&self) -> usize {
        self.m
    }
}

impl<V: Vertex, E: Edge<VType=V>> DirectedGraph<V,E> {
    pub fn new(n: usize) -> Self {
        DirectedGraph {
            n: n,
            m: 0,
            g: vec![Vec::<Eite>::new(); n],
            es: Vec::new(),
            vs: vec![None; n], 
        }
    }

    fn vertex_regist(&mut self, v: V) {
        let i = v.id();
        self.vs[i] = match self.vs[v.id()].take() {
            Some(vv) => {
                assert!(vv.id() == v.id());
                Some(vv)
            }
            None => {
                Some(v)
            }
        }
    }

    pub fn add_edge(&mut self, e: E) {
        let ei = Eite(self.m);
        self.m += 1;
        self.g[e.from().id()].push(ei);
        self.vertex_regist(e.from().clone());
        self.vertex_regist(e.to().clone());
        self.es.push(e);
    }
}

impl<'a, V, E> Directed<'a> for DirectedGraph<V, E> where V: Vertex + 'a, E: Edge<VType=V> + 'a {}

use std::collections::BinaryHeap;
use std::cmp::Ordering;

struct DijkstraNode<W: NNegWeight, V: Vertex> {
    dist: W,
    ver : V,
}

impl<W: NNegWeight, V: Vertex> Ord for DijkstraNode<W, V> {
    fn cmp(&self, other: &Self) -> Ordering {
        other.dist.cmp(&self.dist)
    }
}
impl<W: NNegWeight, V: Vertex> PartialOrd for DijkstraNode<W, V> {
    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
        Some(other.dist.cmp(&self.dist))
    }
}
impl<W: NNegWeight, V: Vertex> PartialEq for DijkstraNode<W, V> {
    fn eq(&self, other: &Self) -> bool {
        self.dist == other.dist
    }
}

impl<W: NNegWeight, V: Vertex> Eq for DijkstraNode<W, V> { }


pub fn dijkstra<'a, G, W, F>(g: &'a G, s: &G::VType, cost: F) -> Properties<W>
where G: Graph<'a>, W: NNegWeight, F: Fn(&G::AEType) -> W { 

    let n = g.v_size();
    let mut dist = Properties::new(n, &W::inf());
    dist[s] = W::zero();

    let mut heap = BinaryHeap::new();
    heap.push(DijkstraNode { dist: dist[s], ver: s.clone() });

    while let Some(DijkstraNode { dist: d, ver: ref v}) = heap.pop() {
        if dist[v] < d { continue }
        for ref e in g.delta(v) {
            if dist[e.from()] + cost(e) < dist[e.to()] {
                dist[e.to()] = dist[e.from()] + cost(e);
                heap.push(DijkstraNode{ dist: dist[e.to()], ver: e.to().clone() })
            }
        }
    }

    dist
}

#[derive(Clone, PartialEq, Eq, Copy)]
enum VIP {
    Yet,
    Used,
}

#[derive(Clone, PartialEq, Eq, Copy)]
struct Ver(usize, VIP);

impl ID for Ver {
    fn id(&self) -> usize {
        self.0 + match self.1 { 
            VIP::Yet => 0,
            VIP::Used => 100000,
        }
    }
} 

fn main() {
    /* input start */ 
    let mut s = String::new();
    std::io::stdin().read_line(&mut s).unwrap();
    let v:Vec<usize> = s.trim().split_whitespace()
        .map(|e|e.parse().unwrap()).collect();
    let (n, m) = (v[0] , v[1]);
    /* input end */
    
    
    let mut g = DirectedGraph::new(200000);

    for _ in 0..m{
        /* input start */
        let mut t = String::new();
        std::io::stdin().read_line(&mut t).unwrap();
        let x:Vec<usize> = t.trim().split_whitespace()
            .map(|e|e.parse().unwrap()).collect();
        let (v, u, d) = (x[0] - 1, x[1] - 1, x[2]);
        /* input end */
        
        g.add_edge((Ver(v, VIP::Yet), Ver(u, VIP::Yet), d));
        g.add_edge((Ver(v, VIP::Used), Ver(u, VIP::Used), d));
        g.add_edge((Ver(v, VIP::Yet), Ver(u, VIP::Used), 0));
        g.add_edge((Ver(u, VIP::Yet), Ver(v, VIP::Yet), d));
        g.add_edge((Ver(u, VIP::Used), Ver(v, VIP::Used), d));
        g.add_edge((Ver(u, VIP::Yet), Ver(v, VIP::Used), 0));
    }
    
    g.add_edge((Ver(0, VIP::Yet), Ver(0, VIP::Used), 0));

    let res = dijkstra(&g, &Ver(0, VIP::Yet), |ep| NNegW::Some(ep.edge().2));
    for i in 0..n {
        let ans = res[&Ver(i, VIP::Yet)] + res[&Ver(i, VIP::Used)];
        if let NNegW::Some(d) = ans {
            println!("{}", d);
        }
    }
}