/*
题目：
寻找图中的最小环，输出路径。
分析：
可以通过枚举删除其中的一条边，看看能否从该边的一点走到另一点，若能并且该最短路的长度加上
删除的边的长度小于当前的最优解的话，更新路径与最优解。而打印路径可以通过数组来表示该点的
前一顶点，然后递归打印路径即可。最短路可以通过dijkstra算法求出。估计的时间复杂度为O(n^2*E)。
我交了一下，用时：1.328 内存：264 KB
*/
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int X = 105;
const int INF = 100000000;
int map[X][X],pre[X],ans[X],dis[X],n,m;
bool use[X];
int dijkstra(int s,int e){ //起点s,终点e
memset(use,false,sizeof(use));
memset(pre,0,sizeof(pre));
for(int i=1;i<=n;i++)
dis[i] = INF;
int MIN,k;
dis[s] = 0;
for(int i=1;i<=n;i++){
MIN = INF;
for(int j=1;j<=n;j++)
if(!use[j]&&dis[j]<MIN)
MIN = dis[k = j];
if(MIN==INF)
return INF;
use[k] = true;
for(int j=1;j<=n;j++)
if(!use[j]&&dis[j]>dis[k]+map[k][j]){
dis[j] = dis[k]+map[k][j];
pre[j] = k; //j的前一顶点为k
}
}
return dis[e];
}
void print(int pos){ //递归打印路径函数
if(!ans[pos])
return;
print(ans[pos]);
printf("%d ",ans[pos]);
}
int main(){
freopen("sum.in","r",stdin);
freopen("sum.out","w",stdout);
int x,y,z;
while(cin>>n,n!=-1){
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
map[i][j] = INF; //题目的输入样例数据中有反向的边输入，并且是无向图
cin>>m;
for(int i=1;i<=m;i++){
scanf("%d%d%d",&x,&y,&z);
if(map[x][y]>z) //小于前面的长度时，更新
map[x][y] = map[y][x] = z;
}
int temp,ret,cnt = INF,pos = -1; //枚举所有的边
for(int j=1;j<=n;j++){
for(int i=1;i<=n;i++){
if(map[j][i]<INF){
temp = map[j][i];
map[j][i] = map[i][j] = INF;
ret = dijkstra(j,i)+temp;
map[j][i] = map[i][j] = temp;
if(ret<cnt){
pos = i;
for(int k=1;k<=n;k++)
ans[k] = pre[k];
cnt = ret;
}
}
}
}
if(pos==-1) //当pos==-1时表示图中没有环
printf("No solution.\n");
else{
print(pos);
cout<<pos<<endl;
}
}
return 0;
}