package main

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

var (
	readString func() string
	readBytes  func() []byte
	stdout     *bufio.Writer
)

func init() {
	readString, readBytes = newReadString(os.Stdin)
	stdout = bufio.NewWriter(os.Stdout)
}

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

	f1 := func() string {
		if !r.Scan() {
			panic("Scan failed")
		}
		return r.Text()
	}
	f2 := func() []byte {
		return []byte(f1())
	}
	return f1, f2
}

func readInt() int {
	return int(readInt64())
}

func readInt64() int64 {
	i, err := strconv.ParseInt(readString(), 10, 64)
	if err != nil {
		panic(err.Error())
	}
	return i
}

func readFloat64() float64 {
	f, err := strconv.ParseFloat(readString(), 64)
	if err != nil {
		panic(err.Error())
	}
	return f
}

func printf(f string, args ...interface{}) (int, error) {
	return fmt.Fprintf(stdout, f, args...)
}

func println(args ...interface{}) (int, error) {
	return fmt.Fprintln(stdout, args...)
}

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")
}

// readString() string
// readInt() int
// readInt64() int64
// readFloat64() float64

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

func mainTA() {
	defer stdout.Flush()
	seed := 12345
	args := os.Args[1:]
	if 1 < len(os.Args) {
		var err error
		seed, err = strconv.Atoi(os.Args[1])
		if err != nil {
			panic(err)
		}
		args = args[1:]
	}
	pi := NewProblemInput(int64(seed), args...)
	println(pi)
}

func mainTB() {
	defer stdout.Flush()
	seed := 12345
	args := os.Args[1:]
	if 1 < len(os.Args) {
		var err error
		seed, err = strconv.Atoi(os.Args[1])
		if err != nil {
			panic(err)
		}
		args = args[1:]
	}
	printf("%d %d", seed, len(args))
	for _, a := range args {
		printf(" %s", a)
	}
	println()
}

func mainA() {
	defer stdout.Flush()
	pi := NewProblemInputFromStdin()
	st := NewStatus(pi)
	for !st.Finished() {
		cmd := st.NextCommand()
		if 0 <= cmd {
			cmd++
		}
		println(cmd)
	}
	eprintln(st.Score())
}

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

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

//
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
}

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)
	}

	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
)

type HeuristicScheduler struct {
	started bool
	Tstart  int
}

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

func (hs *HeuristicScheduler) GetDistance(st *Status, o *Order) int {
	cur, ok := st.CarIsOnVertex()
	assert(ok)

	g := st.g
	if o.loaded {
		return g.distance[cur][o.dst]
	}
	d0 := g.distance[cur][0]
	d1 := g.distance[0][o.dst]
	return d0 + d1
}

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

	return hs.GetDistance(st, p) < hs.GetDistance(st, o)
}

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 HEURISTIC_NR_ORDERS_START <= nrLoaded {
			fl = true
		}
		hs.started = ft && fl
		if !hs.started {
			return st.CarDirection()
		}
	}

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

	st.heads.ForEach(LOADED, func(o *Order) {
		if hs.LessPriority(st, maxo, o) {
			maxo = o
			dst = o.dst
		}
	})

	// need update
	if dst == 0 && cur == 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() *ProblemInput {
	var V, E int
	fmt.Scanf("%d %d", &V, &E)

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

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

	var Tmax int
	fmt.Scanf("%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 NewProblemInputFromStdin() *ProblemInput {
	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,
	}
}

func NewProblemInput(seed int64, args ...string) *ProblemInput {
	Vmax := VMAX_DEFAULT
	Vmin := VMIN_DEFAULT
	Tmax := TMAX_DEFAULT
	if 0 < len(args) {
		v, err := strconv.Atoi(args[0])
		if err != nil {
			panic(err)
		}
		Vmax = int(v)
		Vmin = int(v)
	}
	if 1 < len(args) {
		v, err := strconv.Atoi(args[1])
		if err != nil {
			panic(err)
		}
		Tmax = int(v)
	}
	rand.Seed(seed)

	V := genRandomInt(Vmin, Vmax)

	EMIN := V * 3 / 2
	EMAX := V * 2
	E := genRandomInt(EMIN, EMAX)

	edges := make([][]bool, V+1)
	for i := range edges {
		edges[i] = make([]bool, V+1)
	}

	var u, v, d []int
	e := 0
	{
		vs := make([]int, V)
		for i := range vs {
			vs[i] = i
		}

		shuffled := make([]int, 0, V)
		for i := V - 1; 0 <= i; i-- {
			j := rand.Int() % (i + 1)
			shuffled = append(shuffled, vs[j])
			vs[j], vs[i] = vs[i], vs[j]
		}

		for i := 0; i < V-1; i++ {
			tu := shuffled[i] + 1
			tv := shuffled[i+1] + 1
			td := genRandomInt(1, int(math.Ceil(4*math.Sqrt(float64(2*V)))))
			u = append(u, tu)
			v = append(v, tv)
			d = append(d, td)
			edges[tu][tv] = true
			edges[tv][tu] = true
			e++
		}

		for ; e < E; e++ {
			tu := genRandomInt(1, V)
			tv := genRandomInt(1, V)
			if tu == tv || edges[tu][tv] {
				e-- // retry
				continue
			}
			td := genRandomInt(1, int(math.Ceil(4*math.Sqrt(float64(2*V)))))
			u = append(u, tu)
			v = append(v, tv)
			d = append(d, td)
		}
	}

	Tlast := Tmax / 20 * 19
	Tpeak := genRandomInt(0, Tlast)

	Torder := func(t int) float64 {
		if 0 <= t && t < Tpeak {
			return float64(t) / float64(Tpeak)
		} else if t < Tlast {
			return float64(t) / float64(Tlast-Tpeak)
		}
		return 0
	}

	F := make([]int, V)
	Fa := make([]int, 0)
	for i := range F {
		if i == 0 {
			continue
		}
		F[i] = genRandomInt(FMIN_DEFAULT, FMAX_DEFAULT)
		for j := 0; j < F[i]; j++ {
			Fa = append(Fa, i+1)
		}
	}

	info := make([]ProblemInputInfo, Tmax)
	new_id := 1

	for t := 0; t < Tmax; t++ {
		r := rand.Float64()
		if r < Torder(t) {
			info[t].Nnew = 1
		}
		for i := 0; i < info[t].Nnew; i++ {
			info[t].new_id = append(info[t].new_id, new_id)
			new_id++
			v := Fa[genRandomInt(0, len(Fa)-1)]
			info[t].dst = append(info[t].dst, v)
		}
	}

	return &ProblemInput{
		interactive: false,
		ProblemInputGraph: ProblemInputGraph{
			V: V,
			E: E,

			u: u,
			v: v,
			d: d,
		},
		F:    F,
		Fa:   Fa,
		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
}

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

func mainJ() {
	if len(os.Args) < 2 {
		panic("no input file specified")
	}
	pipath := os.Args[1]
	pir, err := os.Open(pipath)
	assert(err == nil)

	var seed, nargs int
	_, err = fmt.Fscanf(pir, "%d %d", &seed, &nargs)
	assert(err == nil)
	var args []string
	for i := 0; i < nargs; i++ {
		var s string
		_, err = fmt.Fscanf(pir, "%s", &s)
		assert(err == nil)
		args = append(args, s)
	}

	pi := NewProblemInput(int64(seed), args...)
	jd := NewJudge(pi)

	fmt.Println(pi.V, pi.E)
	for i := 0; i < pi.E; i++ {
		fmt.Println(pi.v[i], pi.u[i], pi.d[i])
	}
	sp := ""
	for _, f := range pi.F {
		fmt.Printf("%s%d", sp, f)
		sp = " "
	}
	fmt.Println()
	fmt.Println(pi.Tmax)

	for t, info := range pi.info {
		fmt.Printf("%d\n", info.Nnew)
		for i := 0; i < info.Nnew; i++ {
			fmt.Printf("%d %d\n", info.new_id[i], info.dst[i])
			jd.InputOrder(info.new_id[i], info.dst[i], t)
		}
		puts := jd.GetPutIDs()
		fmt.Printf("%d\n", len(puts))
		for _, id := range puts {
			fmt.Printf("%d\n", id)
		}

		var cmd int
		_, err := fmt.Scanf("%d", &cmd)
		if err != nil {
			fmt.Println("NG")
			panic("NG")
		}
		if 0 <= cmd {
			cmd--
		}
		verdict, achieves := jd.ReceivCommand(cmd)
		if verdict {
			fmt.Println("OK")
		} else {
			fmt.Println("NG")
		}
		fmt.Printf("%d\n", len(achieves))
		for _, id := range achieves {
			fmt.Printf("%d\n", id)
		}
	}
}

func (jd *Judge) GetPutIDs() []int {
	jd.CheckArrivedOrders()
	return jd.CheckStore()
}

func (jd *Judge) CheckStore() []int {
	st := &jd.Status
	if !st.car.OnStore() {
		return nil
	}

	ids := make([]int, 0)
	st.heads.ForEach(IN_STORE, func(o *Order) {
		o.Remove(IN_STORE)
		st.heads.Append(LOADED, o)
		st.vertex[o.dst] = append(st.vertex[o.dst], o)
		ids = append(ids, o.id)
	})
	return ids
}

func (jd *Judge) ReceivCommand(dir int) (bool, []int) {
	st := &jd.Status

	st.SetCarDirection(dir)
	err := st.car.Forward(st.g)
	if err != nil {
		return false, nil
	}

	st.T++
	return true, jd.CheckDoneOrders()
}

func (jd *Judge) CheckDoneOrders() []int {
	st := &jd.Status

	v, ok := st.car.OnVertex()
	if !ok || v == 0 {
		return nil
	}
	ids := make([]int, 0)
	for _, o := range st.vertex[v] {
		st.DoneOrder(o)
		ids = append(ids, o.id)
	}
	st.vertex[v] = st.vertex[v][:0]

	return ids
}

type Judge struct {
	Status
}

func NewJudge(pi *ProblemInput) *Judge {
	jd := &Judge{}

	st := &jd.Status

	st.Scheduler = NewDumbScheduler(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 = 0
	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 jd
}
// vim:set ft=txt:
func main() {
	mainA()
}


Measured memory_bytes: 11008