这题还是再考最短路算法，在这里还是迪杰斯特拉。
但难点在于建图，在这里将同一种种类的传送门具化成一个点，拥有这个传送门的可以通过这个传送门进行到达。但在花费上是二倍。
还有就是不要使用map<pair<int,int>,int>来保存边。这个数据类型操作会导致这道题超时。。。。。。 
//要移动到同一点
//每个点上有一些传送门
//计算1到每个点的最短路和n到每个点的最短路。然后遍历每个点将两个最短路相加求最小的结果
//那么问题就是如何计算最短路。
//每个点都有附属的一些传送门。计算传送门之间的最短路然后让每个点来认领就行。
//什么狗屁附属，不同的传送门其实就是不同点之间的连线，但这连线也会产生重复的，重复的去取最短的那一个即可。
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 2000010;
struct sy{
    int to;
    int next;
    int w;
} edge[2000010];
int head[2000010];
struct Node{
    int number;
    int len;
    bool operator < (const Node& n) const
    {
        return len>n.len;
    }
};
priority_queue<Node> pq;
int n, m;
int cnt = 0;
int vis[maxn];

void add_edge(int x, int y, int w)
{
    edge[++cnt].next = head[x];
    edge[cnt].to = y;
    edge[cnt].w = w;
    head[x] = cnt;
}

void Dijkstra(int bg, int ans[])
{
    memset(vis, 0, sizeof(vis));
    memset(ans, 127, sizeof(vis));
    pq.push({bg, 0});
    ans[bg] = 0;
    while (pq.size())
    {
        int number = pq.top().number;
        pq.pop();
//         cout<<"number="<<number<<" head[number]="<<ans[number]<<endl;
        if (vis[number]) continue;
        vis[number] = true;
        for (int i=head[number];i;i = edge[i].next)
        {
            int next = edge[i].to;
            int w = edge[i].w;
//             cout<<"next="<<next<<endl;
//             cout<<ans[number]+w<<" "<<ans[next]<<endl;
            if (ans[number]+w<ans[next])
            {
                ans[next] = ans[number]+w;
                pq.push({next, ans[next]});
            }
        }
    }
}

signed main()
{
    cin>>n>>m;
    for (int i=1;i<=m;i++)
    {
        int t, s, x;
        cin>>t>>s;
        for (int j=1;j<=s;j++)
        {
            cin>>x;
            add_edge(i+100000, x, t);
            add_edge(x, i+100000, t);
        }
    }
    //接着使用迪杰斯特拉算法求最短路
    int ans_one[maxn];
    int ans_n[maxn];
    Dijkstra(1, ans_one);
    Dijkstra(n, ans_n);
    int ans = INT_MAX;
    //遍历所有的点
    for (int i=1;i<=n;i++)
    {
//         cout<<ans_one[i]<<' '<<ans_n[i]<<endl;
        ans = min(ans, max(ans_one[i],ans_n[i]));
    }
    vector<int> vt;
    //找点
    for (int i=1;i<=n;i++)
    {
        if (max(ans_one[i],ans_n[i])==ans) vt.push_back(i);
    }
    if (ans>=2139062143)
    {
        cout<<-1<<endl;
        return 0;
    }
    cout<<ans/2<<endl;
    vector<int>::iterator vit;
    for (vit = vt.begin();vit!=vt.end();vit++)
    {
        cout<<(*vit)<<' ';
    }
    return 0;
}