#include <bits/stdc++.h>#include <ext/hash_map>#include <ext/hash_set>#include <ext/pb_ds/assoc_container.hpp>#include <ext/pb_ds/priority_queue.hpp>#include <ext/pb_ds/tree_policy.hpp>#include <ext/pb_ds/trie_policy.hpp>#include <ext/pb_ds/tag_and_trait.hpp>const double PI=acos(-1.0);const int MAX=0x7fffffff;const long long MOD=(long long)1E9+7LL;inline double dist(double x1,double y1,double x2,double y2){return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));}//1,2,5,14,42,132,429,1430,4862,16796,58786,208012...//(1)将n+2边形眼弦切割成n个三角形的不同切割数//(2)n+1个数相乘,给每两个元素加上括号的不同方法数//(3)n个节点的不同形状的二叉树数//(4)从n*n方格的左上角移动到右下角不升路径数long long Catalan[1000001];long long Prime[1000001];long long is[1000001];//1,2,3,5,7,11,13,17,19,23long long Fibonacci[1000001];//0,1,1,2,3,5,8,13,21m34,55,89,144,233,377,610...//Numberic Functionstemplate<class T> inline T gcd(T a,T b)//gcd{if(a<0)return gcd(-a,b);if(b<0)return gcd(a,-b);return (b==0)?a:gcd(b,a%b);}template<class T> inline T lcm(T a,T b)//lcm{if(a<0)return lcm(-a,b);if(b<0)return lcm(a,-b);return a*(b/gcd(a,b));}template<class T> inline bool isPrime(T n)//isPrime{if (n <= 1)return false;for (T i = 2; i * i <= n; i++) if (n % i == 0) return false;return true;}template<class T> inline T Euclide(T a, T b, T &x, T &y)//Euclide/extGCD{if (a < 0) {T d = Euclide(-a, b, x, y);x = -x;return d;}if (b < 0) {T d = Euclide(a, -b, x, y);y = -y;return d;}if (b == 0) {x = 1;y = 0;return a;} else {T d = Euclide(b, a % b, x, y);T t = x;x = y;y = t - (a / b) * y;return d;}}template<class T> inline T Eular(T n)//Eular{std::vector<std::pair<T, int> > R = factorize(n);T r = n;for (int i = 0; i < R.size(); i++)r = r / R[i].first * (R[i].first - 1);return r;}template<class T> inline void extGCD(T a, T b, T &x, T &y)//extGCD{T g;if(b == 0){x = 1, y = 0;g = a;return ;}extGCD(b, a % b, y, x);y -= a / b * x;}template<class T> inline T modReverse(T a, T n)//modReverse{T x, y;extGCD(a, n, x, y);return (x + n) % n;}template<class T> inline void g_Catalan()//g_Catalan{Catalan[0] = Catalan[1] = 1LL;for (int i = 2; i < 1000001; i++){T tmp = modReverse(i + 1LL, MOD);Catalan[i] = Catalan[i - 1] * ((i << 2) - 2) % MOD * tmp % MOD;}}template<class T> inline T g_Prime(T n)//g_Prime{T i, j, k = 0;int s, e = (int)(sqrt(0.0 + n) + 1);memset(is, 1, sizeof(is));Prime[k++] = 2; is[0] = is[1] = 0;for(i = 4; i < n; i += 2) is[i] = 0;for(i = 3; i < e; i += 2) if(is[i]) {Prime[k++] = i;for(s = i * 2, j = i * i; j < n; j += s) is[j] = 0;}for(; i < n; i += 2) if(is[i]) Prime[k++] = i;return k;}//Data Structurestd::vector <int> vector_s;std::list <int> list_s;std::deque <int> deque_s;std::stack <int> stack_s;std::queue <int> queue_s;__gnu_cxx::hash_map <char, int> hash_map_s;std::map <char, int> map_s;std::multimap <char, int> multimap_s;__gnu_cxx::hash_set <char, int> hash_set_s;std::set <int> set_s;std::multiset <int> multiset_s;std::priority_queue <int> pr_q;__gnu_pbds::trie <std::string, int> trie_t;__gnu_pbds::tree <int, int, std::less<int>, __gnu_pbds::splay_tree_tag, __gnu_pbds::tree_order_statistics_node_update> sp_t;//Classesclass Susake{//Member access controlprivate :int a;protected :int b;public ://Special member functionsSusake();~Susake();//Overloadlingvoid OP(int);void OP(double);};//Derived classesclass OO : public Susake {};Susake::Susake() {}Susake::~Susake() {}void Susake::OP(int x) {}void Susake::OP(double x) {}//Translatorint isdigit(int c);int isxdigit(int c);int islower(int c);int isupper(int c);int tolower(int c);int toupper(int c);int atoi(const char *nptr);char *itoa(int, const char*, int);//BY_SUSAKEconst long long INF = 1000000000000LL;const int NMAX = 100005;__gnu_pbds::priority_queue<std::pair <int, int>,std::greater<std::pair <int, int> >, __gnu_pbds::pairing_heap_tag > heap;//__gnu_pbds::priority_queue<std::pair<long long, int>, std::vector<std::pair<long long, int> >, std::greater<std::pair<long long, int> > ,__gnu_pbds::pairing_heap_tag >heap;int vert[2 * NMAX], cost[2 * NMAX], next[2 * NMAX], last[2 * NMAX], edge;int u, v, w, n, m, parent[NMAX];long long d[NMAX];void addEdge(int u, int v, int w){    vert[edge] = v;    cost[edge] = w;    next[edge] = last[u];    last[u] = edge ++;}void dijsktra(int s, int t){    memset(d, 63, sizeof(d));    d[s] = 0;    heap.push(std::make_pair(0, s));    int i;    for(;!heap.empty();)    {        u = heap.top().second;        heap.pop();        for(i = last[u]; ~i; i = next[i])        {            v = vert[i], w = cost[i];            if (d[u] + w < d[v]) d[v] = d[u] + w, parent[v] = u, heap.push(std::make_pair(d[v], v));        }    }}int main(int argc, char *argv[]){    memset(last, -1, sizeof(last));    scanf("%d%d", &n, &m);    for(int i = 0; i < m; i++)    {        scanf("%d%d%d", &u, &v, &w);        addEdge(u, v, w);        addEdge(v, u, w);    }    dijsktra(n, 1);    if (parent[1] == 0) puts("-1");    else    {        printf("%d", 1);        u = 1;        while(u != n) u = parent[u], putchar(‘ ‘), printf("%d", u);    }    return 0;}/*int main(int argc, char *argv[]){    char ch, stack[200];    int i = 0, flag = 0, n, j;    scanf("%d%*c", &n);    while(n--){        memset(stack, 0, sizeof(stack));        while (scanf("%c", &ch) != EOF && ch != ‘\n‘){            if (ch == ‘(‘ || ch == ‘[‘){i++;stack[i] = ch;}            else if (ch == ‘)‘ || ch == ‘]‘){                if (stack[i] == ‘(‘ && ch == ‘)‘ || stack[i] == ‘[‘ && ch == ‘]‘) i--;                else flag = 1;}            else flag = 1;        }        printf("%s\n", (i == 0 && flag == 0) ? "Yes" : "No");        flag = 0; i = 0;    }    return 0;}3([])(([()])))([()[]()])()char S[100] = "oooSusakeooo", P[100] = "Susake";int next[100];int KMP(int pos, int len1, int len2){    int i = pos, j = 1, k = 0;    next[1] = 0;    while (j < len1)    if (k == 0 || P[k - 1] == P[j - 1]) j++, k++, next[j] = k;    else k = next[k];    j = 1;    while(i <= len2 && j <= len1){        if (j == 0 || S[i - 1] == P[j - 1]) i++, j++;        else j = next[j];    }    return j > len1 ? i - len1 : 0;}KMP(0, strlen(P), strlen(S));int PreOrder[1000], InOrder[1000];int flag, n;typedef struct BiTNode {    int data;    struct BiTNode *LChild, RChild;} BiTNode, *BiTree;void PostOrderTraverse(BiTree T) {    if(T == NULL) return ;    PostOrderTraverse(T -> LChild);    PostOrderTraverse(T -> RChild);    if(T -> data =http://www.mamicode.com/= PreOrder[0]) printf("%d\n", T -> data);    else printf("%d ", T -> data);}BiTNode *CreatePreTree(int *PreOrder, int *InOrder, int n) {    int i;    BiTNode *pre;    for(i = 0; i < n; ++i) {        if(PreOrder[0] == InOrder[i]) {            pre = (BiTNode *)malloc(sizeof(BiTNode));            pre -> data = http://www.mamicode.com/PreOrder[0];"%d", &n) != EOF) {        for (i = 0; i < n; ++i) scanf("%d", PreOrder + i);        for (i = 0; i < n; ++i) scanf("%d", InOrder + i);        flag = 0;        T = CreatePreTree(PreOrder, InOrder, n);        PostOrderTraverse(T);        destoryBiTree(T);    }    return 0;}74 2 3 1 7 5 63 2 1 4 5 7 63 1 2 5 6 7 4int InOrder[1000], PosterOrder[1000];typedef struct BiTNode {    int data;    struct BiTNode *LChild, *RChild;} BiTNode, *BiTree;int find(int *InOrder, int &x, int n) {    for(int i = 0; i< n; ++i) {if(InOrder[i] == x) return i;}    return -1;}void PreOrderTraverse(BiTree T, int n) {    if(T == NULL) return ;    printf("%d ", T -> data);    PreOrderTraverse(T -> LChild, n);    PreOrderTraverse(T -> RChild, n);}BiTNode *CreateInTree(int *PosterOrder, int *InOrder, int n) {    BiTNode *in;    if(PosterOrder == NULL || InOrder == NULL || n ==0) return NULL;    else {        in = (BiTNode *)malloc(sizeof(BiTNode));        in -> data = http://www.mamicode.com/PosterOrder[n - 1];"%d", &n) != EOF) {        for(i = 0; i < n; i++) scanf("%d", &PosterOrder[i]);        for(i = 0; i < n; i++) scanf("%d", &InOrder[i]);        T = CreateInTree(PosterOrder, InOrder, n);        PreOrderTraverse(T, n);        destoryBiTree(T);        puts("");    }    return 0;}73 1 2 5 6 7 43 2 1 4 5 7 64 2 3 1 7 5 6*/