file_dijkstra.cpp

#include <unistd.h>
#include <stdio.h>
#include <stdlib.h>
#include <sys/sendfile.h>
#include <vector>
#include <set>
#include <limits.h>

using namespace std;

#define BUF_MAX (2 * 1024 * 1024)
int read_char(void) {
    static char buf[BUF_MAX];
    static unsigned int size = 0;
    static unsigned int ptr = 0;
    if (ptr == size) {
        size = read(0, buf, BUF_MAX);
        ptr = 0;
        if (size == 0)
            return -1;
    }
    return buf[ptr++];
}

int read_int(void) {
    int ret = 0;
    int rd = read_char();
    while (rd < '0' || '9' < rd) {
        rd = read_char();
        if (rd == -1)
            return -1;
    }
    while ('0' <= rd && rd <= '9') {
        ret = 10 * ret + rd - '0';
        rd = read_char();
    }
    return ret;
}

#define EDGES_MAX (7 * 1024 * 1024)
struct edge {
    int from, to, cost;
} es[EDGES_MAX];

int edge_cmp(const void *a, const void *b) {
    return ((const edge *)a)->from - ((const edge *)b)->from;
}

void merge(int fptr1, int fptr1e, int fptr2, int fptr2e, int fptr3) {
    while (fptr1 < fptr1e && fptr2 < fptr2e) {
        edge e1, e2;
        fseek(stdout, fptr1, SEEK_SET);
        fread(&e1, sizeof(edge), 1, stdout);
        fseek(stdout, fptr2, SEEK_SET);
        fread(&e2, sizeof(edge), 1, stdout);
        fseek(stdout, fptr3, SEEK_SET);
        if (e1.from < e2.from) {
            fwrite(&e1, sizeof(edge), 1, stdout);
            fptr1 += sizeof(edge);
        } else {
            fwrite(&e1, sizeof(edge), 1, stdout);
            fptr2 += sizeof(edge);
        }
        fptr3 += sizeof(edge);
    }
    while (fptr1 < fptr1e) {
        edge e;
        fseek(stdout, fptr1, SEEK_SET);
        fread(&e, sizeof(edge), 1, stdout);
        fseek(stdout, fptr3, SEEK_SET);
        fwrite(&e, sizeof(edge), 1, stdout);
        fptr1 += sizeof(edge);
        fptr3 += sizeof(edge);
    }
    while (fptr2 < fptr2e) {
        edge e;
        fseek(stdout, fptr2, SEEK_SET);
        fread(&e, sizeof(edge), 1, stdout);
        fseek(stdout, fptr3, SEEK_SET);
        fwrite(&e, sizeof(edge), 1, stdout);
        fptr2 += sizeof(edge);
        fptr3 += sizeof(edge);
    }
}

int main(void) {
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w+", stdout);
    int n = read_int();
    int m = read_int();
    int eptr = 0;
    int part_beg[4];
    int part_end[4];
    int parts = 0;
    int parts_base = 2 * m * sizeof(edge);
    fseek(stdin, parts_base, SEEK_SET);
    for (int i = 0; i < m; ++i) {
        es[eptr].from = read_int();
        es[eptr].to = read_int();
        --es[eptr].from;
        --es[eptr].to;
        es[eptr].cost = read_int();
        ++eptr;
        es[eptr].from = es[eptr - 1].to;
        es[eptr].to = es[eptr - 1].from;
        es[eptr].cost = es[eptr - 1].cost;
        ++eptr;
        if (eptr == EDGES_MAX) {
            qsort(es, EDGES_MAX, sizeof(edge), edge_cmp);
            part_beg[parts] = ftell(stdout);
            fwrite(es, sizeof(edge), EDGES_MAX, stdout);
            part_end[parts] = ftell(stdout);
            ++parts;
            eptr = 0;
        }
    }
    qsort(es, eptr, sizeof(edge), edge_cmp);
    part_beg[parts] = ftell(stdout);
    fwrite(es, sizeof(edge), eptr, stdout);
    part_end[parts] = ftell(stdout);
    ++parts;
    if (parts == 1) {
        off_t off = part_beg[0];
        sendfile(1, 1, &off, part_end[0] - part_beg[0]);
    } else if (parts == 2) {
        merge(part_beg[0], part_end[0], part_beg[1], part_end[1], 0);
    } else if (parts == 3) {
        merge(part_beg[0], part_end[0], part_beg[1], part_end[1], 0);
        off_t off = 0;
        sendfile(1, 1, &off, part_end[0] - part_beg[0] + part_end[1] - part_beg[1]);
        merge(part_beg[0], part_end[1], part_beg[2], part_end[2], 0);
    } else {
        off_t off = 0;
        merge(part_beg[0], part_end[0], part_beg[1], part_end[1], 0);
        sendfile(1, 1, &off, part_end[0] - part_beg[0] + part_end[1] - part_beg[1]);
        merge(part_beg[2], part_end[2], part_beg[3], part_end[3], 0);
        off = 0;
        sendfile(1, 1, &off, part_end[2] - part_beg[2] + part_end[3] - part_beg[3]);
        merge(part_beg[0], part_end[1], part_beg[2], part_end[3], 0);
    }
    vector<int> fbeg(n, -1), fend(n, -1);
    fseek(stdout, 0, SEEK_SET);
    for (int i = 0; i < 2 * m; ++i) {
        edge e;
        fread(&e, sizeof(edge), 1, stdout);
        if (fbeg[e.from] == -1) {
            fbeg[e.from] = ftell(stdout);
        }
        fend[e.from] = ftell(stdout) + sizeof(edge);
    }
    vector<long long int> ans(n, LLONG_MAX);
    vector<int> prev(n, -1);
    ans[0] = 0;
    auto cmp = [&ans](int a, int b) {
        if (ans[a] != ans[b])
            return ans[a] < ans[b];
        return a < b;
    };
    set<int, decltype(cmp)> q(cmp);
    q.insert(0);
    while (!q.empty()) {
        int cur = *q.begin();
        if (cur == n)
            break;
        q.erase(q.begin());
        fseek(stdout, fbeg[cur], SEEK_SET);
        for (int i = fbeg[cur]; i < fend[cur]; i += sizeof(edge)) {
            edge e;
            fread(&e, sizeof(edge), 1, stdout);
            if (ans[e.to] > ans[cur] + e.cost) {
                q.erase(e.to);
                ans[e.to] = ans[cur] + e.cost;
                prev[e.to] = cur;
                q.insert(e.to);
            }
        }
    }
    vector<int> anss;
    anss.reserve(n);
    int cur = n;
    while (cur != -1) {
        anss.push_back(cur);
        cur = prev[cur];
    }
    freopen("output.txt", "w", stdout);
    printf("%ld\n", anss.size());
    for (int i = anss.size() - 1; i >= 0; --i) {
        printf("%d ", anss[i] + 1);
    }
    printf("\n");
}