package main

import (
	"bufio"
	"bytes"
	"container/heap"
	"fmt"
	"io"
	"math"
	"math/rand"
	"os"
	"reflect"
	"runtime"
	"strconv"
	"unsafe"
)

func newReadInt(ior io.Reader) func() int {
	r := bufio.NewScanner(ior)
	r.Buffer(make([]byte, 1024), math.MaxInt32)
	r.Split(bufio.ScanWords)

	readInt := func() int {
		if !r.Scan() {
			panic("Scan failed")
		}
		i, err := strconv.ParseInt(r.Text(), 10, 64)
		if err != nil {
			panic(err.Error())
		}
		return int(i)
	}
	return readInt
}

func newPrinter(iow io.Writer) (func(string, ...interface{}) (int, error), func(...interface{}) (int, error), func()) {
	w := bufio.NewWriter(os.Stdout)
	printf := func(f string, args ...interface{}) (int, error) {
		return fmt.Fprintf(w, f, args...)
	}
	println := func(args ...interface{}) (int, error) {
		return fmt.Fprintln(w, args...)
	}
	flush := func() {
		w.Flush()
	}
	return printf, println, flush
}

func eprintln(args ...interface{}) (int, error) {
	return fmt.Fprintln(os.Stderr, args...)
}

func eprintf(f string, args ...interface{}) (int, error) {
	return fmt.Fprintf(os.Stderr, f, args...)
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

func min64(a, b int64) int64 {
	if a < b {
		return a
	}
	return b
}

func max(a, b int) int {
	if a < b {
		return b
	}
	return a
}

func max64(a, b int64) int64 {
	if a < b {
		return b
	}
	return a
}

func abs(a int) int {
	if a < 0 {
		return -a
	}
	return a
}

func abs64(a int64) int64 {
	if a < 0 {
		return -a
	}
	return a
}

func gcd(a, b int) int {
	if b == 0 {
		return a
	}
	return gcd(b, a%b)
}

func gcd64(a, b int64) int64 {
	if b == 0 {
		return a
	}
	return gcd64(b, a%b)
}

func assert(exp bool) {
	if exp {
		return
	}
	pc, file, line, _ := runtime.Caller(1)
	fmt.Fprintf(os.Stderr, "ASSERT! %s:%d @0x%x", file, line, pc)
	panic("assert")
}

// -----------------------------------------------------------------------------

func mainA(w io.Writer, r io.Reader) {
	bw := bufio.NewWriter(w)
	defer bw.Flush()

	pi := NewProblemInputBuffered(r)
	st := NewStatus(pi)
	for !st.Finished() {
		cmd := st.NextCommand()
		if 0 <= cmd {
			cmd++
		}
		fmt.Fprintln(bw, cmd)
	}
}

func mainB(w io.Writer, r io.Reader) {
	pi := NewProblemInputInteractive(r)
	st := NewStatus(pi)
	for t := 0; !st.Finished(); t++ {
		var Nnew, new_id, dst int
		fmt.Fscanf(r, "%d", &Nnew)
		for i := 0; i < Nnew; i++ {
			fmt.Fscanf(r, "%d %d", &new_id, &dst)
			st.InputOrder(new_id, dst, t)
		}
		var Nput, put_id int
		fmt.Fscanf(r, "%d", &Nput)
		for i := 0; i < Nput; i++ {
			fmt.Fscanf(r, "%d", &put_id)
		}
		cmd := st.NextCommand()
		if 0 <= cmd {
			cmd++
		}
		fmt.Fprintln(w, cmd)
		var verdict string
		fmt.Fscanf(r, "%s", &verdict)
		if verdict != "OK" {
			eprintln("WA")
			return
		}
		var Nachieve, achieve_id int
		fmt.Fscanf(r, "%d", &Nachieve)
		for i := 0; i < Nachieve; i++ {
			fmt.Fscanf(r, "%d", &achieve_id)
		}
	}
}

// -----------------------------------------------------------------------------

//
type Car struct {
	direction int
	src, dst  int
	togo      int
}

func NewCar(pi *ProblemInput) *Car {
	car := &Car{
		direction: -1,
	}
	return car
}

func (car *Car) String() string {
	sp := stringerPrefix
	w := new(bytes.Buffer)
	fmt.Fprintf(w, "%sCar:\n", sp)
	sp = sp + "  "
	fmt.Fprintf(w, "%sdirection: %d\n", sp, car.direction)
	fmt.Fprintf(w, "%ssrc: %d\n", sp, car.src)
	fmt.Fprintf(w, "%sdst: %d\n", sp, car.dst)
	fmt.Fprintf(w, "%stogo: %d\n", sp, car.togo)
	return w.String()
}

func (car *Car) SetDirection(dir int) {
	car.direction = dir
}

func (car *Car) Direction() int {
	return car.direction
}

func (car *Car) OnVertex() (int, bool) {
	if car.togo != 0 {
		return -1, false
	}
	return car.dst, true
}

func (car *Car) OnVertexId(i int) bool {
	return car.dst == i && car.togo == 0
}

func (car *Car) OnStore() bool {
	v, ok := car.OnVertex()
	return ok && v == 0
}

func (car *Car) Forward(g *Graph) error {
	if car.direction == -1 {
		return nil
	}

	if car.direction != car.dst {
		if car.togo == 0 || car.direction == car.src {
			car.src = car.dst
			car.dst = car.direction
			d := g.edgeLength[car.src][car.dst]
			car.togo = d - car.togo
		} else {
			return fmt.Errorf("WA: \n%s", car)
		}
	}
	car.togo = max(0, car.togo-1)
	return nil
}

// -----------------------------------------------------------------------------

type Graph struct {
	t    int
	V, E int

	edges      [][]Edge
	edgeLength [][]int

	distance [][]int
	prevs    [][]int
	neighbor [][]int
}

func NewGraph(pi *ProblemInput) *Graph {
	g := &Graph{}
	g.V = pi.V
	g.E = pi.E

	g.edges = make([][]Edge, g.V)
	g.edgeLength = make([][]int, g.V)
	for i := 0; i < g.V; i++ {
		g.edges[i] = make([]Edge, 0)
		g.edgeLength[i] = make([]int, g.V)
	}
	for i := 0; i < g.E; i++ {
		u := pi.u[i] - 1
		v := pi.v[i] - 1
		d := pi.d[i]

		g.edges[u] = append(g.edges[u], Edge{v, d})
		g.edges[v] = append(g.edges[v], Edge{u, d})

		g.edgeLength[u][v] = d
		g.edgeLength[v][u] = d
	}

	g.distance = make([][]int, g.V)
	g.prevs = make([][]int, g.V)
	for i := 0; i < g.V; i++ {
		g.distance[i], g.prevs[i] = Dijkstra(g.edges, i, true)
	}

	g.neighbor = make([][]int, g.V)
	for i := range g.neighbor {
		a := make([]int, g.V)
		for j := range a {
			a[j] = j
		}
		Sort(a, func(j, k int) bool {
			x, y := a[j], a[k]
			return g.distance[i][x] < g.distance[i][y]
		})
		g.neighbor[i] = a
	}

	return g
}

func (g *Graph) NextHop(cur, dst int) int {
	res := dst
	for g.prevs[cur][res] != cur {
		res = g.prevs[cur][res]
	}
	return res
}

// -----------------------------------------------------------------------------

// Scheduler determins the next command
type Scheduler interface {
	Schedule(st *Status) int
}

type DumbScheduler struct {
}

func (ds *DumbScheduler) Schedule(st *Status) int {
	cur, ok := st.CarIsOnVertex()
	if !ok {
		return st.CarDirection()
	}
	// need update
	dst := st.Destination()
	if dst == 0 && cur == 0 {
		return -1
	}

	return st.g.NextHop(cur, dst)
}

func NewDumbScheduler(in *ProblemInput) *DumbScheduler {
	ds := &DumbScheduler{}
	return ds
}

// -----------------------------------------------------------------------------

// heuristic scheduler
const (
	HEURISTIC_T_START             = 100
	HEURISTIC_NR_ORDERS_START     = 10
	HEURISTIC_STORE_DISTANT_RATIO = 0.5
)

type HeuristicScheduler struct {
	started       bool
	Tstart        int
	NROrdersStart int
	heading0      bool
}

func NewHeuristicScheduler(pi *ProblemInput) *HeuristicScheduler {
	Tstart := min(HEURISTIC_T_START, pi.Tmax/100)
	//NROrdersStart := min(HEURISTIC_NR_ORDERS_START, pi.Tmax/20*19/2/100)
	NROrdersStart := HEURISTIC_NR_ORDERS_START
	hs := &HeuristicScheduler{
		Tstart:        Tstart,
		NROrdersStart: NROrdersStart,
	}
	return hs
}

func (st *Status) GetDistance(from int, o *Order) int {
	g := st.g
	if o.loaded {
		return g.distance[from][o.dst]
	}

	d0 := g.distance[from][0]
	if st.T < o.gend {
		d0 = max(d0, o.gend-st.T)
	}
	d1 := g.distance[0][o.dst]
	return d0 + d1
}

func (st *Status) LessPriority(cur int, o, p *Order) bool {
	if o == nil {
		return true
	}
	if p == nil {
		return false
	}

	pd := st.GetDistance(cur, p)
	od := st.GetDistance(cur, o)

	return pd < od
}

func (hs *HeuristicScheduler) Schedule(st *Status) int {
	cur, ok := st.CarIsOnVertex()
	if !ok {
		return st.CarDirection()
	}

	if !hs.started {
		var ft, fl bool
		if hs.Tstart <= st.T {
			ft = true
		}
		var nrLoaded int
		st.heads.ForEach(LOADED, func(o *Order) {
			nrLoaded++
		})
		if hs.NROrdersStart <= nrLoaded {
			fl = true
		}
		hs.started = ft && fl
		if !hs.started {
			return st.CarDirection()
		}
	}

	if hs.heading0 {
		if cur != 0 {
			return st.g.NextHop(cur, 0)
		} else {
			hs.heading0 = false
		}
	}

	var maxo *Order
	var dst int

	for i := st.nextOrder; i < len(st.orders); i++ {
		o := &st.orders[i]
		if st.LessPriority(cur, maxo, o) {
			maxo = o
			dst = 0
		}
	}

	var nrStore int
	st.heads.ForEach(IN_STORE, func(o *Order) {
		nrStore++
		if st.LessPriority(cur, maxo, o) {
			maxo = o
			dst = 0
		}
	})

	var nrLoaded int
	st.heads.ForEach(LOADED, func(o *Order) {
		nrLoaded++
		if st.LessPriority(cur, maxo, o) {
			maxo = o
			dst = o.dst
		}
	})

	if dst != 0 {
		if nrLoaded < nrStore {
			hs.heading0 = true
			dst = 0
		}
	}

	// need update
	if dst == cur {
		assert(dst == 0)
		return -1
	}

	return st.g.NextHop(cur, dst)
}

// -----------------------------------------------------------------------------

const (
	DONE = iota
	IN_STORE
	LOADED
	LIST_MAX
)

var LIST_NAMES = []string{
	"DONE",
	"IN_STORE",
	"LOADED",
}

type List struct {
	prev *Order
	next *Order
}

type Order struct {
	id     int
	dst    int
	gend   int
	done   int
	loaded bool
	list   [LIST_MAX]List
}

func NewOrder(id, dst, gend int) Order {
	o := Order{
		id:   id,
		dst:  dst,
		gend: gend,
		done: 1000000007,
	}
	// list cannot be initialized until appended to st.orders
	return o
}

//
// List operations
//

func (o *Order) Remove(l int) {
	prev := o.list[l].prev
	next := o.list[l].next

	next.list[l].prev = prev
	prev.list[l].next = next

	o.list[l].prev = o
	o.list[l].next = o
	assert(o.list[l].next != nil)
}

func (head *Order) MoveAll(from, to int) {
	if head.list[from].next == head {
		return
	}

	// append 'to' list first
	tail := head.list[to].prev
	head.ForEach(from, func(o *Order) {
		tail.list[to].next = o
		o.list[to].prev = tail
		tail = o
	})
	tail.list[to].next = head
	head.list[to].prev = tail

	// remove from 'from'
	head.list[from].next = head
	head.list[from].prev = head
}

func (head *Order) Append(l int, o *Order) {
	tail := head.list[l].prev

	tail.list[l].next = o
	head.list[l].prev = o

	o.list[l].prev = tail
	o.list[l].next = head
}

func (head *Order) ForEach(l int, f func(o *Order)) {
	assert(head.list[l].next != nil)
	o := head.list[l].next
	next := o.list[l].next
	for o != head {
		assert(o != nil)
		f(o)
		o = next
		next = next.list[l].next
	}

}

func (o *Order) InitializeList() {
	for i := 0; i < LIST_MAX; i++ {
		o.list[i].prev = o
		o.list[i].next = o
	}
}

func (o *Order) FinishDerivery(done int) {
	o.done = done
	for i := 0; i < LIST_MAX; i++ {
		if i == DONE {
			continue
		}
		o.Remove(i)
	}
}

// -----------------------------------------------------------------------------

// Status represents a status of the car
type Status struct {
	Scheduler

	g   *Graph
	car *Car

	orders    []Order
	nextOrder int

	T     int
	Tlast int
	Tmax  int

	// list heads
	heads  Order
	vertex [][]*Order
}

func NewStatus(pi *ProblemInput) *Status {
	st := &Status{}

	st.Scheduler = NewHeuristicScheduler(pi)

	st.g = NewGraph(pi)
	st.car = NewCar(pi)

	st.orders = make([]Order, 0, st.Tlast+5)
	for t, info := range pi.info {
		for j := 0; j < info.Nnew; j++ {
			st.InputOrder(info.new_id[j], info.dst[j], t)
		}
	}
	st.nextOrder = 0

	st.T = -1
	st.Tmax = pi.Tmax
	st.Tlast = pi.Tmax / 100 * 95

	for i := 0; i < LIST_MAX; i++ {
		st.heads.list[i].next = &st.heads
		st.heads.list[i].prev = &st.heads
	}

	st.vertex = make([][]*Order, pi.V)
	for i := range st.vertex {
		st.vertex[i] = make([]*Order, 0)
	}

	return st
}

var stringerPrefix string

func (st *Status) String() string {
	sp := stringerPrefix
	w := new(bytes.Buffer)
	fmt.Fprintf(w, "%sStatus:", sp)
	sp = sp + "  "
	fmt.Fprintf(w, "%sT=%d Tmax=%d Tlast=%d\n", sp, st.T, st.Tmax, st.Tlast)
	fmt.Fprintf(w, "%slen(orders): %d\n", sp, len(st.orders))
	fmt.Fprintf(w, "%snextOrder: %d\n", sp, st.nextOrder)
	destsLoaded := make([]int, 0)

	for i := 0; i < LIST_MAX; i++ {
		fmt.Fprintf(w, "%sheads.list[%s]:", sp, LIST_NAMES[i])
		for o := st.heads.list[i].next; o != &st.heads; o = o.list[i].next {
			if i == LOADED {
				destsLoaded = append(destsLoaded, o.dst)
			}
			fmt.Fprintf(w, " %d", o.id)
		}
		fmt.Fprintf(w, "\n")
	}

	fmt.Fprintf(w, "%sDestination: %d (", sp, st.Destination())
	for s, d := st.car.src, st.Destination(); s != d; s = st.g.NextHop(s, d) {
		fmt.Fprintf(w, " %d", s)
	}
	fmt.Fprintf(w, ")\n")

	for _, v := range destsLoaded {
		fmt.Fprintf(w, "%sVertex[%d]:", sp, v)
		for _, o := range st.vertex[v] {
			fmt.Fprintf(w, " %d", o.id)
		}
		fmt.Fprintf(w, "\n")
	}

	stringerPrefix = sp
	car := fmt.Sprintf("%s", st.car)
	stringerPrefix = sp[:len(sp)-2]
	fmt.Fprintf(w, "%s", car)
	return w.String()
}

func (st *Status) NextCommand() int {
	//eprintln("Start----")
	//eprintln(st)
	st.Prepare()
	//eprintln("Prepared----")
	//eprintln(st)
	dir := st.Schedule(st)
	//eprintln("dir: ", dir)
	st.SetCarDirection(dir)
	//eprintln("Directed----")
	//eprintln(st)
	st.Fixup()
	//eprintln("Forwarded----")
	//eprintln(st)
	return dir
}

func (st *Status) SetCarDirection(dir int) {
	st.car.SetDirection(dir)
}

func (st *Status) CarDirection() int {
	return st.car.Direction()
}

func (st *Status) Finished() bool {
	return st.Tmax <= st.T+1
}

func (st *Status) CarIsOnVertex() (int, bool) {
	return st.car.OnVertex()
}

func (st *Status) ListIsEmpty(l int) bool {
	return st.heads.list[l].next == &st.heads
}

func (st *Status) Destination() int {
	if st.ListIsEmpty(LOADED) {
		return 0
	}
	return st.heads.list[LOADED].next.dst
}

func (st *Status) InputOrder(new_id, dst, t int) {
	o := NewOrder(new_id, dst-1, t)
	st.orders = append(st.orders, o)
	st.orders[len(st.orders)-1].InitializeList()
}

func (st *Status) Prepare() {
	st.T++
	st.CheckArrivedOrders()
	st.CheckDoneOrders()
	st.CheckStore()
}

func (st *Status) Fixup() {
	err := st.car.Forward(st.g)
	if err != nil {
		msg := fmt.Sprintf("WA: \n%s", st)
		panic(msg)
	}
}
func (st *Status) ArriveOrder(o *Order) {
	st.heads.Append(IN_STORE, o)
}

func (st *Status) CheckArrivedOrders() {
	var i int
	assert(st.heads.list[IN_STORE].next != nil)
	for i = st.nextOrder; i < len(st.orders) && st.orders[i].gend <= st.T; i++ {
		o := &st.orders[i]
		st.ArriveOrder(o)
	}
	st.nextOrder = i
}

func (st *Status) DoneOrder(o *Order) {
	o.FinishDerivery(st.T)
	st.heads.Append(DONE, o)
}

func (st *Status) CheckDoneOrders() {
	v, ok := st.car.OnVertex()
	if !ok || v == 0 {
		return
	}
	for _, o := range st.vertex[v] {
		st.DoneOrder(o)
	}
	st.vertex[v] = st.vertex[v][:0]
}

func (st *Status) CheckStore() {
	if !st.car.OnStore() {
		return
	}

	st.heads.ForEach(IN_STORE, func(o *Order) {
		o.Remove(IN_STORE)
		o.loaded = true
		st.heads.Append(LOADED, o)
		st.vertex[o.dst] = append(st.vertex[o.dst], o)
	})
}

func (st *Status) Score() int64 {
	var score int64
	st.heads.ForEach(DONE, func(o *Order) {
		t1 := int64(st.Tmax)
		t2 := int64(o.done - o.gend)
		score += t1*t1 - t2*t2
	})
	return score
}

// -----------------------------------------------------------------------------

//
// GenInput
//

const (
	VMIN_DEFAULT = 200
	VMAX_DEFAULT = 400
	TMAX_DEFAULT = 10000
	FMIN_DEFAULT = 1
	FMAX_DEFAULT = 2
)

type ProblemInput struct {
	interactive bool
	seed        int64
	ProblemInputGraph
	F    []int
	Fa   []int
	Fsum int
	Tmax int
	info []ProblemInputInfo
}

func (pi *ProblemInput) String() string {
	buf := new(bytes.Buffer)
	fmt.Fprintf(buf, "%d %d\n", pi.V, pi.E)
	for i := range pi.u {
		fmt.Fprintf(buf, "%d %d %d\n", pi.u[i], pi.v[i], pi.d[i])
	}
	fmt.Fprintf(buf, "%d\n", pi.Tmax)
	for i := 0; i < pi.Tmax; i++ {
		fmt.Fprintf(buf, "%d\n", pi.info[i].Nnew)
		for j := 0; j < pi.info[i].Nnew; j++ {
			fmt.Fprintf(buf, "%d %d\n", pi.info[i].new_id[j], pi.info[i].dst[j])
		}
	}

	return buf.String()
}

type ProblemInputB ProblemInput

func (pi *ProblemInputB) String() string {
	buf := new(bytes.Buffer)
	fmt.Fprintf(buf, "%d %d\n", pi.V, pi.E)
	for i := range pi.u {
		fmt.Fprintf(buf, "%d %d %d\n", pi.u[i], pi.v[i], pi.d[i])
	}
	sp := ""
	for _, f := range pi.F {
		fmt.Fprintf(buf, "%s%d", sp, f)
		sp = " "
	}
	fmt.Fprintf(buf, "\n")
	fmt.Fprintf(buf, "%d\n", pi.Tmax)
	for i := 0; i < pi.Tmax; i++ {
		fmt.Fprintf(buf, "%d\n", pi.info[i].Nnew)
		for j := 0; j < pi.info[i].Nnew; j++ {
			fmt.Fprintf(buf, "%d %d\n", pi.info[i].new_id[j], pi.info[i].dst[j])
		}
	}

	return buf.String()
}

type ProblemInputGraph struct {
	V, E int

	u []int
	v []int
	d []int
}

type ProblemInputInfo struct {
	Nnew   int
	new_id []int
	dst    []int
}

func genRandomInt(low, high int) int {
	return rand.Int()%(high-low+1) + low
}

func NewProblemInputInteractive(r io.Reader) *ProblemInput {
	var V, E int
	fmt.Fscanf(r, "%d %d", &V, &E)

	u := make([]int, E)
	v := make([]int, E)
	d := make([]int, E)
	for i := 0; i < E; i++ {
		fmt.Fscanf(r, "%d %d %d", &u[i], &v[i], &d[i])
	}

	F := make([]int, V)
	var Fsum int
	for i := range F {
		var f int
		fmt.Fscanf(r, "%d", &f)
		F[i] = f
		Fsum += f
	}

	var Tmax int
	fmt.Fscanf(r, "%d", &Tmax)

	return &ProblemInput{
		interactive: true,
		ProblemInputGraph: ProblemInputGraph{
			V: V,
			E: E,
			u: u,
			v: v,
			d: d,
		},
		F:    F,
		Fsum: Fsum,
		Tmax: Tmax,
	}
}

func NewProblemInputBuffered(ior io.Reader) *ProblemInput {
	readInt := newReadInt(ior)

	V := readInt()
	E := readInt()
	u := make([]int, E)
	v := make([]int, E)
	d := make([]int, E)
	for i := 0; i < E; i++ {
		u[i] = readInt()
		v[i] = readInt()
		d[i] = readInt()
	}
	Tmax := readInt() // fixed 10000
	info := make([]ProblemInputInfo, Tmax)
	for i := 0; i < Tmax; i++ {
		info[i].Nnew = readInt()
		for j := 0; j < info[i].Nnew; j++ {
			info[i].new_id = append(info[i].new_id, readInt())
			info[i].dst = append(info[i].dst, readInt())
		}
	}

	return &ProblemInput{
		interactive: false,
		ProblemInputGraph: ProblemInputGraph{
			V: V,
			E: E,
			u: u,
			v: v,
			d: d,
		},
		Tmax: Tmax,
		info: info,
	}
}

func NewProblemInputFromReader(r io.Reader) *ProblemInput {
	var V, E int
	fmt.Fscanf(r, "%d %d", &V, &E)

	u := make([]int, E)
	v := make([]int, E)
	d := make([]int, E)
	for i := 0; i < E; i++ {
		fmt.Fscanf(r, "%d %d %d", &u[i], &v[i], &d[i])
	}
	var Tmax int
	fmt.Fscanf(r, "%d", &Tmax)

	info := make([]ProblemInputInfo, Tmax)
	for i := 0; i < Tmax; i++ {
		fmt.Fscanf(r, "%d", &info[i].Nnew)
		for j := 0; j < info[i].Nnew; j++ {
			var new_id, dst int
			fmt.Fscanf(r, "%d %d", &new_id, &dst)
			info[i].new_id = append(info[i].new_id, new_id)
			info[i].dst = append(info[i].dst, dst)
		}
	}

	return &ProblemInput{
		interactive: false,
		ProblemInputGraph: ProblemInputGraph{
			V: V,
			E: E,
			u: u,
			v: v,
			d: d,
		},
		Tmax: Tmax,
		info: info,
	}
}

// ----------------------------------------------------------------------------

type Edge struct {
	to, cost int
}

type DijkstraPriorityQueue []Edge

func (pq DijkstraPriorityQueue) Len() int {
	return len(pq)
}

func (pq DijkstraPriorityQueue) Less(i, j int) bool {
	return pq[i].cost < pq[j].cost
}

func (pq DijkstraPriorityQueue) Swap(i, j int) {
	pq[i], pq[j] = pq[j], pq[i]
}

func (pq *DijkstraPriorityQueue) Push(x interface{}) {
	old := *pq
	*pq = append(old, x.(Edge))
}

func (pq *DijkstraPriorityQueue) Pop() interface{} {
	old := *pq
	n := len(old) - 1
	x := old[n]
	*pq = old[:n]
	return x
}

func Dijkstra(G [][]Edge, start int, needPrev bool) ([]int, []int) {

	pq := new(DijkstraPriorityQueue)
	push := func(to, cost int) {
		heap.Push(pq, Edge{to, cost})
	}
	pop := func() (int, int) {
		x := heap.Pop(pq).(Edge)
		return x.to, x.cost
	}
	empty := func() bool {
		return pq.Len() == 0
	}

	N := len(G)
	costs := make([]int, N)
	for i := range costs {
		costs[i] = math.MaxInt32
	}
	costs[start] = 0

	var prev []int
	if needPrev {
		prev = make([]int, N)
		for i := range prev {
			prev[i] = -1
		}
		prev[start] = start
	}

	push(start, 0)

	for !empty() {
		v, d := pop()
		if costs[v] < d {
			continue
		}
		for _, e := range G[v] {
			u, nd := e.to, e.cost+costs[v]
			if costs[u] < nd {
				continue
			}
			costs[u] = nd
			if needPrev {
				prev[u] = v
			}
			push(u, nd)
		}
	}

	return costs, prev
}

// =============================================================================

// Copyright 2017 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

// name of functions are changed

// The function panics if the provided interface is not a slice.
func Sort(slice interface{}, less func(i, j int) bool) {
	rv := reflect.ValueOf(slice)
	swap := _sort_Swapper(slice)
	length := rv.Len()
	_sort_quickSort_func(_sort_lessSwap{less, swap}, 0, length, _sort_maxDepth(length))
}

func _sort_maxDepth(n int) int {
	var depth int
	for i := n; i > 0; i >>= 1 {
		depth++
	}
	return depth * 2
}

type _sort_lessSwap struct {
	Less func(i, j int) bool
	Swap func(i, j int)
}

// Auto-generated variant of sort.go:insertionSort
func _sort_insertionSort_func(data _sort_lessSwap, a, b int) {
	for i := a + 1; i < b; i++ {
		for j := i; j > a && data.Less(j, j-1); j-- {
			data.Swap(j, j-1)
		}
	}
}

// Auto-generated variant of sort.go:siftDown
func _sort_siftDown_func(data _sort_lessSwap, lo, hi, first int) {
	root := lo
	for {
		child := 2*root + 1
		if child >= hi {
			break
		}
		if child+1 < hi && data.Less(first+child, first+child+1) {
			child++
		}
		if !data.Less(first+root, first+child) {
			return
		}
		data.Swap(first+root, first+child)
		root = child
	}
}

// Auto-generated variant of sort.go:heapSort
func _sort_heapSort_func(data _sort_lessSwap, a, b int) {
	first := a
	lo := 0
	hi := b - a
	for i := (hi - 1) / 2; i >= 0; i-- {
		_sort_siftDown_func(data, i, hi, first)
	}
	for i := hi - 1; i >= 0; i-- {
		data.Swap(first, first+i)
		_sort_siftDown_func(data, lo, i, first)
	}
}

// Auto-generated variant of sort.go:medianOfThree
func _sort_medianOfThree_func(data _sort_lessSwap, m1, m0, m2 int) {
	if data.Less(m1, m0) {
		data.Swap(m1, m0)
	}
	if data.Less(m2, m1) {
		data.Swap(m2, m1)
		if data.Less(m1, m0) {
			data.Swap(m1, m0)
		}
	}
}

// Auto-generated variant of sort.go:doPivot
func _sort_doPivot_func(data _sort_lessSwap, lo, hi int) (midlo, midhi int) {
	m := int(uint(lo+hi) >> 1)
	if hi-lo > 40 {
		s := (hi - lo) / 8
		_sort_medianOfThree_func(data, lo, lo+s, lo+2*s)
		_sort_medianOfThree_func(data, m, m-s, m+s)
		_sort_medianOfThree_func(data, hi-1, hi-1-s, hi-1-2*s)
	}
	_sort_medianOfThree_func(data, lo, m, hi-1)
	pivot := lo
	a, c := lo+1, hi-1
	for ; a < c && data.Less(a, pivot); a++ {
	}
	b := a
	for {
		for ; b < c && !data.Less(pivot, b); b++ {
		}
		for ; b < c && data.Less(pivot, c-1); c-- {
		}
		if b >= c {
			break
		}
		data.Swap(b, c-1)
		b++
		c--
	}
	protect := hi-c < 5
	if !protect && hi-c < (hi-lo)/4 {
		dups := 0
		if !data.Less(pivot, hi-1) {
			data.Swap(c, hi-1)
			c++
			dups++
		}
		if !data.Less(b-1, pivot) {
			b--
			dups++
		}
		if !data.Less(m, pivot) {
			data.Swap(m, b-1)
			b--
			dups++
		}
		protect = dups > 1
	}
	if protect {
		for {
			for ; a < b && !data.Less(b-1, pivot); b-- {
			}
			for ; a < b && data.Less(a, pivot); a++ {
			}
			if a >= b {
				break
			}
			data.Swap(a, b-1)
			a++
			b--
		}
	}
	data.Swap(pivot, b-1)
	return b - 1, c
}

// Auto-generated variant of sort.go:quickSort
func _sort_quickSort_func(data _sort_lessSwap, a, b, maxDepth int) {
	for b-a > 12 {
		if maxDepth == 0 {
			_sort_heapSort_func(data, a, b)
			return
		}
		maxDepth--
		mlo, mhi := _sort_doPivot_func(data, a, b)
		if mlo-a < b-mhi {
			_sort_quickSort_func(data, a, mlo, maxDepth)
			a = mhi
		} else {
			_sort_quickSort_func(data, mhi, b, maxDepth)
			b = mlo
		}
	}
	if b-a > 1 {
		for i := a + 6; i < b; i++ {
			if data.Less(i, i-6) {
				data.Swap(i, i-6)
			}
		}
		_sort_insertionSort_func(data, a, b)
	}
}

// ----------------------------------------------------------------------------

func _sort_Swapper(slice interface{}) func(i, j int) {
	v := reflect.ValueOf(slice)
	vdata := v.Pointer()
	vlen := v.Len()
	vcap := v.Cap()

	sz := int(v.Type().Elem().Size())

	// for typical small elements
	switch sz {
	case 24: // for slice
		var s [][3]int64
		h := (*reflect.SliceHeader)(unsafe.Pointer(&s))
		h.Data = vdata
		h.Len = vlen
		h.Cap = vcap
		return func(i, j int) { s[i], s[j] = s[j], s[i] }
	case 16: // for string
		var s [][2]int64
		h := (*reflect.SliceHeader)(unsafe.Pointer(&s))
		h.Data = vdata
		h.Len = vlen
		h.Cap = vcap
		return func(i, j int) { s[i], s[j] = s[j], s[i] }
	case 8:
		var s []int64
		h := (*reflect.SliceHeader)(unsafe.Pointer(&s))
		h.Data = vdata
		h.Len = vlen
		h.Cap = vcap
		return func(i, j int) { s[i], s[j] = s[j], s[i] }
	case 4:
		var s []int32
		h := (*reflect.SliceHeader)(unsafe.Pointer(&s))
		h.Data = vdata
		h.Len = vlen
		h.Cap = vcap
		return func(i, j int) { s[i], s[j] = s[j], s[i] }
	case 2:
		var s []int16
		h := (*reflect.SliceHeader)(unsafe.Pointer(&s))
		h.Data = vdata
		h.Len = vlen
		h.Cap = vcap
		return func(i, j int) { s[i], s[j] = s[j], s[i] }
	case 1:
		var s []int8
		h := (*reflect.SliceHeader)(unsafe.Pointer(&s))
		h.Data = vdata
		h.Len = vlen
		h.Cap = vcap
		return func(i, j int) { s[i], s[j] = s[j], s[i] }
	}

	// for large elements
	if sz%16 == 0 {
		m := sz / 16
		var s [][2]int64
		h := (*reflect.SliceHeader)(unsafe.Pointer(&s))
		h.Data = vdata
		h.Len = vlen * m
		h.Cap = vcap * m
		return func(i, j int) {
			for k := 0; k < m; k++ {
				ri := i*m + k
				rj := j*m + k
				s[ri], s[rj] = s[rj], s[ri]
			}
		}
	}
	if sz%8 == 0 {
		m := sz / 8
		var s []int64
		h := (*reflect.SliceHeader)(unsafe.Pointer(&s))
		h.Data = vdata
		h.Len = vlen * m
		h.Cap = vcap * m
		return func(i, j int) {
			for k := 0; k < m; k++ {
				ri := i*m + k
				rj := j*m + k
				s[ri], s[rj] = s[rj], s[ri]
			}
		}
	}
	if sz%4 == 0 {
		m := sz / 4
		var s []int32
		h := (*reflect.SliceHeader)(unsafe.Pointer(&s))
		h.Data = vdata
		h.Len = vlen * m
		h.Cap = vcap * m
		return func(i, j int) {
			for k := 0; k < m; k++ {
				ri := i*m + k
				rj := j*m + k
				s[ri], s[rj] = s[rj], s[ri]
			}
		}
	}
	if sz%2 == 0 {
		m := sz / 2
		var s []int16
		h := (*reflect.SliceHeader)(unsafe.Pointer(&s))
		h.Data = vdata
		h.Len = vlen * m
		h.Cap = vcap * m
		return func(i, j int) {
			for k := 0; k < m; k++ {
				ri := i*m + k
				rj := j*m + k
				s[ri], s[rj] = s[rj], s[ri]
			}
		}
	} else {
		m := sz
		var s []int8
		h := (*reflect.SliceHeader)(unsafe.Pointer(&s))
		h.Data = vdata
		h.Len = vlen * m
		h.Cap = vcap * m
		return func(i, j int) {
			for k := 0; k < m; k++ {
				ri := i*m + k
				rj := j*m + k
				s[ri], s[rj] = s[rj], s[ri]
			}
		}
	}
}

// =============================================================================
// vim:set ft=txt:
func main() {
	mainA(os.Stdout, os.Stdin)
}


Measured memory_bytes: 11776