program name
    implicit none
    type edge
        integer(8):: to
        integer(8):: w
    end type
    type node
        integer(8):: num
        type(edge),allocatable:: e(:)
    end type
    type(node),allocatable:: tree(:)
    integer(8):: n
    integer(8):: u,v,w
    integer(8):: i,dst
    integer(4),allocatable:: color(:)
    logical,allocatable:: is_passed(:)

    read*, n
    allocate(tree(n),color(n),is_passed(n))
    call init_tree(tree)

    do i=1,n-1
        read*, u,v,w
        call append(tree(u),v,w)
        call append(tree(v),u,w)
    end do

    ! do i=1,n
    !     print*, '---'
    !     print*, i
    !     print*, tree(i)%e(:)%to
    !     print*, tree(i)%e(:)%w
    ! end do
    dst=0
    is_passed(:) = .false.
    call dtm_color(tree(1),dst)

    do i=1,n
        print*, color(i)
    end do
contains
    recursive subroutine dtm_color(n,d)
        type(node):: n
        integer(8):: d,i
        ! print*, n%num,d
        is_passed(n%num) = .true.
        color(n%num) = mod(d,2_8)
        
        do i=1,size(n%e)
            if (.not.is_passed(n%e(i)%to)) call dtm_color(tree(n%e(i)%to), d+n%e(i)%w)
        end do
    end subroutine


    subroutine init_tree(t)
        type(node):: t(:)
        integer(8):: i

        do i=1,size(t)
            allocate(t(i)%e(0))
            t(i)%num = i
        end do
    end subroutine

    
    subroutine append(n,to,w)
        type(node),intent(inout):: n
        integer(8),intent(in):: to,w
        type(edge),allocatable:: tmp(:)

        allocate(tmp(size(n%e)))
        tmp(:) = n%e(:)
        deallocate(n%e)
        allocate(n%e(size(tmp)+1))
        n%e(:size(tmp)) = tmp(:)
        n%e(size(n%e))%to = to
        n%e(size(n%e))%w = w
        deallocate(tmp)
    end subroutine
end program name