module mod_graph
  implicit none
  integer(8), parameter :: inf = 1000000000000000000_8

  type item
    integer :: id = 0
    integer(8) :: wt = 0_8
  end type

  type priorityqueue
    integer :: num = 0
    type(item), pointer :: heap(:) => null()
  end type

  type edge
    integer :: to = 0
    integer(8) :: wt = 0_8
  end type

  type arraylist
    integer :: num = 0
    type(edge), pointer :: arr(:) => null()
  end type

  type graph
    type(arraylist), pointer :: egs(:) => null()
  contains
    procedure :: addedge => addedge
    procedure :: add => add
    procedure :: dijkstra => dijkstra
  end type

  interface graph
    module procedure :: newg
  end interface graph

contains

  function newi(id,wt) result(ret)
    integer, intent(in) :: id
    integer(8), intent(in) :: wt
    type(item) :: ret
    ret%id = id
    ret%wt = wt
  end

  subroutine swapi(a,b)
    type(item), intent(inout) :: a, b
    type(item) :: c
    c = a
    a = b
    b = c
  end

  subroutine appendi(a)
    type(item), pointer, intent(inout) :: a(:)
    integer :: n
    type(item), allocatable :: tmp(:)
    n = size(a)
    allocate(tmp(n))
    tmp = a
    deallocate(a)
    allocate(a(2*n))
    a(1:n) = tmp
    deallocate(tmp)
  end

  function lessi(a,b) result(ret)
    type(item), intent(in) :: a, b
    logical :: ret
    ret = a%wt < b%wt
  end

  subroutine finalizei(pq)
    type(priorityqueue), intent(inout) :: pq
    if (associated(pq%heap)) deallocate(pq%heap)
    pq%num = 0
  end

  subroutine offer(pq,it)
    type(priorityqueue), intent(inout) :: pq
    type(item), intent(in) :: it
    integer :: i, j
    if (.not.associated(pq%heap)) allocate(pq%heap(1))
    if (pq%num == size(pq%heap)) call appendi(pq%heap)
    pq%num = pq%num+1
    pq%heap(pq%num) = it
    i = pq%num
    do while (i > 1)
      j = i/2
      if (lessi(pq%heap(i),pq%heap(j))) call swapi(pq%heap(i),pq%heap(j))
      i = j
    end do
  end

  function poll(pq) result(ret)
    type(priorityqueue), intent(inout) :: pq
    type(item) :: ret
    integer :: n, i, j
    n = pq%num
    ret = pq%heap(1)
    pq%heap(1) = pq%heap(n)
    pq%num = pq%num-1
    i = 1
    do while (2*i < n)
      j = 2*i
      if (j+1 < n .and. lessi(pq%heap(j+1),pq%heap(j))) j = j+1
      if (lessi(pq%heap(j),pq%heap(i))) call swapi(pq%heap(j),pq%heap(i))
      i = j
    end do
  end

  function newe(to,wt) result(ret)
    integer, intent(in) :: to
    integer(8), intent(in) :: wt
    type(edge) :: ret
    ret%to = to
    ret%wt = wt
  end

  subroutine appende(a)
    type(edge), pointer, intent(inout) :: a(:)
    integer :: n
    type(edge), allocatable :: tmp(:)
    n = size(a)
    allocate(tmp(n))
    tmp = a
    deallocate(a)
    allocate(a(2*n))
    a(1:n) = tmp
    deallocate(tmp)
  end

  subroutine finalizee(list)
    type(arraylist), intent(inout) :: list
    if (associated(list%arr)) deallocate(list%arr)
    list%num = 0
  end

  subroutine adde(list,e)
    type(arraylist), intent(inout) :: list
    type(edge), intent(in) :: e
    if (.not.associated(list%arr)) allocate(list%arr(1))
    if (list%num == size(list%arr)) call appende(list%arr)
    list%num = list%num+1
    list%arr(list%num) = e
  end

  function newg(n) result(ret)
    integer, intent(in) :: n
    type(graph) :: ret
    allocate(ret%egs(n))
  end

  subroutine addedge(g,fm,e)
    class(graph), intent(inout) :: g
    integer, intent(in) :: fm
    type(edge), intent(in) :: e
    call adde(g%egs(fm),e)
  end

  subroutine add(g,fm,to,wt)
    class(graph), intent(inout) :: g
    integer, intent(in) :: fm, to
    integer(8) :: wt
    call adde(g%egs(fm),newe(to,wt))
  end

  function dijkstra(g,s) result(ret)
    class(graph), intent(inout) :: g
    integer, intent(in) :: s
    integer(8) :: ret(size(g%egs))
    type(priorityqueue) :: pq
    type(item) :: it
    type(edge) :: e
    integer :: i
    ret = inf
    ret(s) = 0_8
    call offer(pq,newi(s,ret(s)))
    do while (pq%num > 0)
      it = poll(pq)
      if (it%wt > ret(it%id)) cycle
      do i = 1, g%egs(it%id)%num
        e = g%egs(it%id)%arr(i)
        if (ret(e%to) > ret(it%id)+e%wt) then
          ret(e%to) = ret(it%id)+e%wt
          call offer(pq,newi(e%to,ret(e%to)))
        end if
      end do
    end do
  end

end module mod_graph

program saving_snuuk
  use mod_graph
  implicit none
  integer(8), parameter :: dyen = 1000000000000000_8
  integer :: n, m, s, t, u, v, i
  integer(8) :: a, b, cy(100000) = 0_8, cs(100000) = 0_8, ans(100000) = 0_8
  type(graph) :: gy, gs
  read(*,*) n, m, s, t
  gy = graph(n)
  gs = graph(n)
  do i = 1, m
    read(*,*) u, v, a, b
    call gy%add(u,v,a)
    call gy%add(v,u,a)
    call gs%add(u,v,b)
    call gs%add(v,u,b)
  end do
  cy(1:n) = gy%dijkstra(s)
  cs(1:n) = gs%dijkstra(t)
  ans(n) = cy(n)+cs(n)
  do i = n-1, 1, -1
    ans(i) = min(ans(i+1),cy(i)+cs(i))
  end do
  do i = 1, n
    write(*,'(i0)') dyen-ans(i)
  end do
end program saving_snuuk

Measured memory_bytes: 27308