Language: C

#include <assert.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define range(i, a, b) for (int i = (a); i < (b); i++)
#define rep(i, b) for (int i = 0; i < (b); i++)

#define MAX_V 400
#define MAX_LV 400
#define MAX_T 10000
#define WS 5
#define WH 1

typedef struct T {
	short h;
	long long s;
} T;

typedef struct U {
	short t, v;
} U;

short V, e;
short ord[MAX_V][MAX_LV];
short ord_size[MAX_V];

int m[MAX_V][MAX_V], sp[MAX_V][MAX_V];
short prev[MAX_V][MAX_V];

T dp[MAX_T][MAX_V];
short idx[MAX_T][MAX_V][MAX_LV];
short nidx[MAX_LV];

U path[MAX_T][MAX_V];

long long maxi;
int cnt;

short vs[MAX_T];
short len;

long long eval(T *a, T *b) {
	return (a->s * WS + a->h * WH) - (b->s * WS + b->h * WH);
}

int solve() {
	rep(i, MAX_T) rep(j, MAX_V) path[i][j] = (U){-1, -1};
	rep(i, MAX_T) rep(j, MAX_V) dp[i][j] = (T){-1, -1};
	dp[0][0] = (T){0, 0};

	rep(t, MAX_T) {
		// if (t % 100 == 0) show(t);
		// if(r(mt) * t >  1000000) continue;
		rep(from, V) {
			// if(r(mt) < 200 and i != 0) continue;
			if (dp[t][from].h == -1) continue;
			 if (maxi - 1000 > dp[t][from].s) continue;

			T n_dp = dp[t][from];
			memcpy(nidx, idx[t][from], sizeof(nidx));

			//short V_lim = V; // + sqrt(50) * t / 2 / 1000.0;
			range(j, 0, fmin(V,100)) {
				short to;
				if (j == -1) {
					to = 0;
				} else {
					to = sp[from][j];
					//printf("%d %d\n", to, j);
				}
				short n_time = m[from][to] + t;
				if (n_time >= MAX_T) break;

				short idx_save = nidx[to];
				short h_save = n_dp.h;
				long long s_save = n_dp.s;

				if (to == 0) {
					n_dp.h = n_time;
				} else {
					// printf("%d %d\n", ord[v][nidx[v]], nc.h);
					while (nidx[to] < ord_size[to] &&
						   ord[to][nidx[to]] <= n_dp.h) {
						long long wt = n_time - ord[to][nidx[to]];
						// printf("%d\n",n_dp.s);
						n_dp.s += 1;//00000000 - wt * wt;
						nidx[to]++;
					}
				}

				if (eval(&n_dp, &dp[n_time][to]) > 0LL) {
					dp[n_time][to] = n_dp;
					memcpy(idx[n_time][to], nidx, sizeof(nidx));
					path[n_time][to] = (U){t, from};
				}

				maxi = fmax(maxi, n_dp.s);

				nidx[to] = idx_save;
				n_dp.h = h_save;
				n_dp.s = s_save;
			}
		}
	}

	long long maxi = 0;
	U c;
	rep(i, MAX_T) {
		// printf("\nt = %d\n",i);
		rep(j, V) {
			// T t = dp[i][j];
			// printf("%d %d %lld\n", t.h, j, t.s);
			if (maxi < dp[i][j].s) {
				maxi = dp[i][j].s;
				c = (U){i, j};
			}
		}
	}

	while (path[c.t][c.v].v != -1) {
		T t = dp[c.t][c.v];
		// printf("timr:%d have:%d node:%d score:%lld\n", c.t, t.h, c.v, t.s);
		vs[len++] = c.v;
		c = path[c.t][c.v];
	}
	vs[len++] = c.v;

	// rep(i, len) { printf("%d ", vs[i]); }
	// puts("");

	//printf("%lld\n", maxi);
	return maxi;
}

void init() {
	rep(i, V) rep(j, V) m[i][j] = 1e9;
	rep(i, V) m[i][i] = 0;
	rep(i, V) rep(j, V) prev[i][j] = i;
}

void warshallFloyd() {
	rep(k, V) {
		rep(i, V) {
			rep(j, V) {
				if (m[i][j] > m[i][k] + m[k][j]) {
					m[i][j] = m[i][k] + m[k][j];
					prev[i][j] = prev[k][j];
				}
			}
		}
	}
	rep(i, V) m[i][i] = 1e3;
	m[0][0] = 1;
}

short s_path[MAX_V][MAX_V][MAX_V];
short s_path_size[MAX_V][MAX_V];

void sPath(int s, int g) {
	int cur, len = 0;
	for (cur = g; cur != s; cur = prev[s][cur]) s_path[g][s][len++] = cur;
	s_path[g][s][len++] = s;

	s_path_size[g][s] = len;
}

void read() {
	scanf("%hd%hd", &V, &e);
	init();
	rep(i, e) {
		short a, b, c;
		scanf("%hd%hd%hd", &a, &b, &c);
		a--;
		b--;
		m[a][b] = m[b][a] = c;
	}
	warshallFloyd();

	short t;
	scanf("%hd", &t);
	for (short i = 0; i < t; i++) {
		short n;
		scanf("%hd", &n);
		if (n) {
			short a;
			scanf("%*hd%hd", &a);
			a--;
			// printf(" --- %hd %hd\n",a, i);
			ord[a][ord_size[a]++] = i;
		}
	}
	rep(i, V) { cnt += ord_size[i]; }
	fprintf(stderr, "%d\n",cnt);
	//printf("%d\n", cnt);
}

typedef struct P {
	int dis, v;
} P;
int compare(const void *p1, const void *p2) {
	return ((P *)p1)->dis - ((P *)p2)->dis;
}

void init_sp() {
	P s[V][V];
	rep(i, V) {
		rep(j, V) {
			s[i][j].dis = m[i][j];
			s[i][j].v = j;
		}
	}
	rep(i, V) {
		qsort((void *)s[i], (size_t)V, sizeof(P *), compare);
		rep(j, V) { sp[i][j] = s[i][j].v; }
	}
	rep(i,V){
		rep(j,V){
			sPath(i,j);
		}
	}
}

void output() {
	//printf("%d\n",len);
	//for (int i = len - 1; i >= 0; i--) { printf("%d- ", vs[i]); } puts("");
	short vp[MAX_T], l = 0;
	for (int i = len - 1; i > 0; i--) {
		short from = vs[i], to = vs[i - 1];
		if(s_path_size[from][to] == 1){
			//printf("%d ", s_path[from][to][0]);
			vp[l++] = s_path[from][to][0];
		}else{
			rep(j,s_path_size[from][to] - (i == 1 ? 0 : 1)){
				vp[l++] = s_path[from][to][j];
				//printf("%d ", s_path[from][to][j]);
			}
		}
	}

	int need = MAX_T;
	rep(i,l-1){
		if(vp[i] == vp[i+1]){
			printf("-1\n");
			need--;
		}else{
			need -= m[vp[i]][vp[i+1]];
			rep(_,m[vp[i]][vp[i+1]]) printf("%d\n",vp[i + 1]+1);
		}
	}
	assert(need >= 0);
	while(need-- > 0) printf("-1\n");
}

signed main() {
	read();
	init_sp();
	solve();
	output();

	// read();
	// solve(T(0, 0, 0), 0);
}


Compiler output:
/tmp/cc1dmxwW.o: in function `solve':
main.c:(.text+0xac): relocation truncated to fit: R_X86_64_PC32 against symbol `path' defined in .bss section in /tmp/cc1dmxwW.o
main.c:(.text+0xe9): relocation truncated to fit: R_X86_64_PC32 against symbol `path' defined in .bss section in /tmp/cc1dmxwW.o
main.c:(.text+0x239): relocation truncated to fit: R_X86_64_PC32 against symbol `maxi' defined in .bss section in /tmp/cc1dmxwW.o
main.c:(.text+0x314): relocation truncated to fit: R_X86_64_PC32 against symbol `nidx' defined in .bss section in /tmp/cc1dmxwW.o
main.c:(.text+0x3d7): relocation truncated to fit: R_X86_64_PC32 against symbol `nidx' defined in .bss section in /tmp/cc1dmxwW.o
main.c:(.text+0x421): relocation truncated to fit: R_X86_64_PC32 against symbol `nidx' defined in .bss section in /tmp/cc1dmxwW.o
main.c:(.text+0x483): relocation truncated to fit: R_X86_64_PC32 against symbol `nidx' defined in .bss section in /tmp/cc1dmxwW.o
main.c:(.text+0x499): relocation truncated to fit: R_X86_64_PC32 against symbol `nidx' defined in .bss section in /tmp/cc1dmxwW.o
main.c:(.text+0x4ae): relocation truncated to fit: R_X86_64_PC32 against symbol `nidx' defined in .bss section in /tmp/cc1dmxwW.o
main.c:(.text+0x4e2): relocation truncated to fit: R_X86_64_PC32 against symbol `nidx' defined in .bss section in /tmp/cc1dmxwW.o
main.c:(.text+0x60a): additional relocation overflows omitted from the output
/usr/bin/ld: main.c:(.text+0x6c5): undefined reference to `fmax'
/usr/bin/ld: main.c:(.text+0x73a): undefined reference to `fmin'
collect2: error: ld returned 1 exit status