using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.IO;

namespace AtCoder
{
    public class State
    {
        public long time;

        public readonly long tlast;

        public readonly long tmax;

        public readonly long tmax2p;

        public State(long tmax)
        {
            this.time = 0;
            this.tmax = tmax;
            this.tmax2p = tmax * tmax;
            this.tlast = (long)((double)tmax * 0.95);
        }

        public State Tick(long tnew)
        {
            var res = new State(tmax);
            res.time = tnew;
            return res;
        }
    }

    public class MainClass
    {
        public static void Main(string[] args)
        {
            try
            {
                var first = new FirstInput();
                var graph = Funcs.BuildGraph(first);
                var state = new State(first.Tmax);

                var prepareOdrs = new List<Order>(); //準備中の注文
                var carringOdrs = new List<Order>(); //配送中の注文

                for (int t = 0; t < first.Tmax; t++)
                {
                    var orderIn = new OrdersInput(t);
                    if (orderIn.order != null) prepareOdrs.Add(orderIn.order);

                    if (orderIn.puts.Count > 0)
                    {
                        carringOdrs.AddRange(prepareOdrs);
                        prepareOdrs.Clear();
                    }

                    state.time = t;

                    Console.WriteLine(Drive(
                        graph, carringOdrs, prepareOdrs, state, orderIn.order != null ? 1 : 0));

                    var verdict = new VerdictInput();
                    if (verdict.verdict != "OK") break;

                    if (verdict.archives.Count > 0)
                        carringOdrs.RemoveAll(o => verdict.archives.Contains(o.id));
                }
            }
            catch (Exception e)
            {
                Console.WriteLine(e);
            }
        }

        ///<summary>ルート</summary>
        private static Queue<Order[]> route = null;

        ///<summary>車</summary>
        private static readonly Car car = new Car();

        private static Order[] Nearest = null;

        private static string Drive(List<Vertex> graph, List<Order> carringOdrs, List<Order> prepareOdrs, State state, int nNew)
        {
            if (car.Returned)
            {
                if (carringOdrs.Count == 0) return "-1";

                var list = Funcs.BuildRoute(graph, carringOdrs, state);

                if (list.Count > 200 && state.time < state.tlast)
                {
                    var drop = (int)(list.Count * 0.2);
                    var nearList = list
                        .Select((g, n) => Tuple.Create(graph[g[0].dst], n, g))
                        .Take(list.Count - drop)
                        .Skip(drop)
                        .Where(t => t.Item1.Distances[0] < t.Item1.Distances[list[t.Item2 + 1][0].dst])
                        .ToList();

                    Nearest = null;
                    if (nearList.Count > 0)
                        Nearest = nearList.MinBy(t => t.Item1.Distances[0]).Item3;
                }

                route = new Queue<Order[]>(list);
                car.SetDest(route.Dequeue()[0].dst);
            }
            else if (car.Arrived)
            {
                if (route.Count == 0)
                    car.Return();
                else
                {
                    if (Nearest != null &&
                            car.headingVId == Nearest[0].dst &&
                            Funcs.ReturnIsBetter(graph, route, prepareOdrs, state, graph[car.headingVId]))
                        car.Return();
                    else
                        car.SetDest(route.Dequeue()[0].dst);
                }
            }

            return car.Drive(graph);
        }
    }

    public static class Funcs
    {
        public static void Assert(bool cond) { if (!cond) throw new Exception(); }

        public static bool ReturnIsBetter(List<Vertex> graph, Queue<Order[]> route,
            List<Order> prepareOdrs, State state, Vertex now)
        {
            var nextOdrs = prepareOdrs.ToList();
            nextOdrs.AddRange(route.SelectMany(g => g));

            var r1 = CalcScore2(graph, new List<Order[]>(), nextOdrs, state, now);
            var r0 = CalcScore2(graph, route.ToList(), prepareOdrs, state, now);

            var p0 = (double)r0.Score / (double)r0.Dist;
            var p1 = (double)r1.Score / (double)r1.Dist;
            return p1 > p0 * 1.05;
        }

        private static RouteRes CalcScore2(
            List<Vertex> graph, List<Order[]> nowRoute, List<Order> prepareOdrs, State state, Vertex now)
        {
            var nextState = state.Tick(state.time + CalcTotalLength(graph, nowRoute, now));
            var nextRoute = BuildRoute(graph, prepareOdrs, nextState);
            var r2 = CalcScore(graph, nextRoute, nextState);// TODO nextのscoreはもっと大きい
            if (nowRoute.Count == 0) return r2;

            var r1 = CalcScore(graph, nowRoute, state, now);
            return new RouteRes(r1.Score + r2.Score, r1.Dist + r2.Dist);
        }

        public static List<Order[]> BuildRoute(
            List<Vertex> graph, List<Order> carringOdrs, State state, Vertex start = null)
        {
            var carring = carringOdrs.GroupBy(o => o.dst).Select(g => g.ToArray()).ToList();
            var list = new List<Order[]>();

            if (list.Count == 1) return list;

            // Nearest Neighbour 法
            var now = (start != null) ? start : graph[0];
            while (carring.Count > 0)
            {
                var nearest = carring.MinBy(g => now.Distances[g[0].dst]);
                carring.Remove(nearest);
                list.Add(nearest);
                now = graph[nearest[0].dst];
            }

            // 2-opt 法
            int ai = 0, bi = 0;
            Func<int, int> Reverse = n => (n >= ai && n <= bi) ? bi - (n - ai) : n;

            if (state.time < state.tlast)
            {
                var dist = CalcTotalLength(graph, list, start);

                bool changed = false;
                do
                {
                    // TODO 後続の点数が減らない程度の距離延長を許容し、点数を上げる
                    changed = false;
                    for (int w = list.Count - 1; w >= 1; w--)
                    {
                        for (int n = 0; n < list.Count - w; n++)
                        {
                            ai = n;
                            bi = n + w;

                            var revdDist = CalcTotalLength(graph, list, start, Reverse);

                            if (dist > revdDist)
                            {
                                list.Reverse(ai, bi - ai + 1);
                                dist = revdDist;
                                changed = true;
                            }
                        }
                    }
                } while (changed);
            }
            else
            {
                var rr = CalcScore(graph, list, state, start);

                bool changed = false;
                do
                {
                    changed = false;
                    for (ai = 0; ai < list.Count - 1; ai++)
                    {
                    RESTART:
                        for (bi = ai + 1; bi < list.Count; bi++)
                        {
                            var revdRr = CalcScore(graph, list, state, start, Reverse);

                            if (rr.Score < revdRr.Score)
                            {
                                list.Reverse(ai, bi - ai + 1);
                                rr = revdRr;
                                changed = true;
                                goto RESTART;
                            }
                        }
                    }
                } while (changed);
            }

            return list;
        }

        // private static long CalcScore(bool evalScore,
        //     List<Vertex> graph, List<IGrouping<int, Order>> list, State state, Vertex now = null, Func<int, int> seq = null)
        // {
        //     if (evalScore)
        //         return CalcScore(graph, list, state, now, seq);
        //     else
        //         return -CalcTotalLength(graph, list, now, seq);
        // }

        public struct RouteRes
        {
            public readonly long Score;
            public readonly long Dist;

            public RouteRes(long s, long d)
            {
                Score = s;
                Dist = d;
            }
        }

        /// <summary>
        /// 指定した位置(デフォルトは店)から届け先を回り終わった時点のスコアを計算する。
        /// </summary>
        public static RouteRes CalcScore(
            List<Vertex> graph, List<Order[]> list, State state, Vertex now = null, Func<int, int> seq = null)
        {
            var score = 0L;
            var time = state.time;
            var tmax2p = state.tmax2p;

            if (now == null) now = graph[0];

            for (int i = 0; i < list.Count; i++)
            {
                var idx = seq?.Invoke(i) ?? i;
                if (idx < 0) continue;

                var g = list[idx];

                time += now.Distances[g[0].dst];

                foreach (var o in g)
                {
                    var late = time - o.time;
                    score += tmax2p - late * late;
                }

                now = graph[g[0].dst];
            }

            time += now.Distances[graph[0].Id];
            time -= state.time;

            return new RouteRes(score, time);
        }

        /// <summary>
        /// 指定した位置(デフォルトは店)から店に帰還するまでの距離を計算する。
        /// </summary>
        public static long CalcTotalLength(
            List<Vertex> graph, List<Order[]> list, Vertex now = null, Func<int, int> seq = null)
        {
            var time = 0L;

            if (now == null) now = graph[0];
            for (int i = 0; i < list.Count; i++)
            {
                var idx = seq?.Invoke(i) ?? i;
                if (idx < 0) continue;

                var g = list[idx];
                time += now.Distances[g[0].dst];

                now = graph[g[0].dst];
            }

            time += now.Distances[graph[0].Id];

            return time;
        }

        public static List<Vertex> BuildGraph(FirstInput f)
        {
            checked
            {
                var template = new int[f.sizeV];
                for (int i = 0; i < template.Length; i++) template[i] = 91200 + 91200;

                var vertices = Enumerable
                    .Range(0, f.sizeV)
                    .Select(n => new Vertex(n, (int[])template.Clone()))
                    .ToList();

                foreach (var side in f.sides)
                {
                    var u = vertices[side.u];
                    var v = vertices[side.v];
                    u.Adjacent.Add(v);
                    v.Adjacent.Add(u);
                    u.Distances[v.Id] = side.distance;
                    v.Distances[u.Id] = side.distance;
                }

                // 全頂点に対しダイクストラ法を適用
                foreach (var start in vertices)
                {
                    start.Distances[start.Id] = 0;
                    var queue = new Queue<Vertex>(start.Adjacent);

                    while (queue.Count > 0)
                    {
                        var vertex = queue.Dequeue();

                        if (!vertex.Adjacent.Contains(start))
                        {
                            vertex.Distances[start.Id] =
                                vertex.Adjacent.Min(t => t.Distances[start.Id] + t.Distances[vertex.Id]);
                        }

                        foreach (var t in vertex.Adjacent)
                        {
                            if (t.Distances[start.Id] > vertex.Distances[start.Id] + vertex.Distances[t.Id])
                            {
                                queue.Enqueue(t);
                            }
                        }
                    }
                }

                return vertices;
            }
        }
    }

    public class Car
    {
        /// <summary>最終目的地。</summary>
        private int destVId = 0;

        /// <summary>現在の移動先。destVId と同値になり得る。</summary>
        public int headingVId { get; private set; } = 0;

        /// <summary>headingVId との距離。距離0で到着、その次に各移動先が切り替わる。</summary>
        private int headingVDist = 0;

        /// <summary>最終目的地に到着した。</summary>
        public bool Arrived => destVId == headingVId && headingVDist == 0;

        /// <summary>店にいる。</summary>
        public bool Returned => Arrived && destVId == 0;

        public void Return()
        {
            destVId = 0;
        }

        public void SetDest(int dest)
        {
            destVId = dest;
        }

        public string Drive(List<Vertex> graph)
        {
            if (Arrived) return "-1";

            if (headingVDist == 0)
            {
                var next = graph[headingVId].Adjacent.MinBy(t => t.Distances[destVId]);

                headingVDist = next.Distances[headingVId] - 1;
                headingVId = next.Id;
            }
            else
                headingVDist--;

            return (headingVId + 1).ToString();
        }
    }

    public class Vertex
    {
        public readonly int Id;
        public readonly List<Vertex> Adjacent;

        // TODO ushort
        public readonly int[] Distances;

        public Vertex(int id, int[] d)
        {
            this.Id = id;
            this.Adjacent = new List<Vertex>();
            this.Distances = d;
        }
    }

    #region "入出力"

    ///<summary>辺の入力。</summary>
    public class Side
    {
        public readonly int u;
        public readonly int v;
        public readonly int distance;

        public Side()
        {
            var ary = Console.ReadLine().Split();
            u = int.Parse(ary[0]) - 1;
            v = int.Parse(ary[1]) - 1;
            distance = int.Parse(ary[2]);
        }
    }

    public class FirstInput
    {
        public readonly int sizeV;
        private readonly int sizeE;
        ///<summary>辺の集合。</summary>
        public readonly List<Side> sides;
        ///<summary>注文頻度。</summary>
        public readonly List<int> freqs;
        public readonly int Tmax;

        public FirstInput()
        {
            var ary = Console.ReadLine().Split();
            sizeV = int.Parse(ary[0]);
            sizeE = int.Parse(ary[1]);

            sides = EnumerablePlus.Repeat(sizeE, () => new Side()).ToList();
            freqs = Console.ReadLine().Split().Select(int.Parse).ToList();
            Tmax = int.Parse(Console.ReadLine());
        }
    }

    public class Order
    {
        ///<summary>注文ID。</summary>
        public readonly int id;

        ///<summary>届け先頂点。</summary>
        public readonly int dst;

        ///<summary>受注時間。</summary>
        public readonly int time;

        public Order(int time)
        {
            var ary = Console.ReadLine().Split();
            id = int.Parse(ary[0]);
            dst = int.Parse(ary[1]) - 1;
            this.time = time;
        }

        public Order(int id, int dst, int time)
        {
            this.id = id;
            this.dst = dst;
            this.time = time;
        }
    }

    public class OrdersInput
    {
        // TODO 0 or 1
        private readonly int sizeNew;
        ///<summary>新規注文。</summary>
        public readonly Order order;
        private readonly int sizePut;
        ///<summary>出荷開始注文。</summary>
        public readonly List<int> puts;

        public OrdersInput(int time)
        {
            sizeNew = int.Parse(Console.ReadLine());
            if (sizeNew == 1)
                order = new Order(time);
            else
                order = null;
            sizePut = int.Parse(Console.ReadLine());
            puts = EnumerablePlus.Repeat(sizePut, () => int.Parse(Console.ReadLine())).ToList();
        }
    }

    public class VerdictInput
    {
        public readonly string verdict;
        private readonly int sizeArchive = 0;
        public readonly List<int> archives = null;

        public VerdictInput()
        {
            verdict = Console.ReadLine();

            if (verdict != "OK") return;

            sizeArchive = int.Parse(Console.ReadLine());
            archives = EnumerablePlus.Repeat(sizeArchive, () => int.Parse(Console.ReadLine())).ToList();
        }
    }

    #endregion

    public static class EnumerablePlus
    {
        ///<summary>出力文字列に変換。</summary>
        public static string MkString<T>(this IEnumerable<T> list)
        {
            return list.Aggregate(
                new System.Text.StringBuilder(),
                (a, b) => ((a.Length > 0) ? a.Append(' ') : a).Append(b)
                ).ToString();
        }

        ///<summary>添字付きfor。</summary>
        public static void ForEach<T>(this IEnumerable<T> list, Action<T, int> a)
        {
            int i = 0;
            foreach (var item in list)
            {
                a(item, i);
            }
        }

        ///<summary>添字付きfor。</summary>
        public static void ForEach<T>(this IEnumerable<T> list, Action<T> a)
        {
            foreach (var item in list)
            {
                a(item);
            }
        }

        ///<summary>指定回数デリゲートを呼び出す。</summary>
        public static IEnumerable<T> Repeat<T>(int n, Func<T> f)
        {
            for (int i = 0; i < n; i++)
            {
                yield return f();
            }
        }

        public static T MinBy<T, U>(this IEnumerable<T> xs, Func<T, U> key) where U : IComparable<U>
        {
            return xs.Aggregate((a, b) => key(a).CompareTo(key(b)) <= 0 ? a : b);
        }

        public static T MaxBy<T, U>(this IEnumerable<T> xs, Func<T, U> key) where U : IComparable<U>
        {
            return xs.Aggregate((a, b) => key(a).CompareTo(key(b)) >= 0 ? a : b);
        }
    }
}


Measured memory_bytes: 38924