/*Citat din mesajul lui: Philip din Martie 09, 2009, 19:13:05
Se poate sa existe drumuri minime pentru care nici un tip de lanterna nu este posibil, atunci programul meu fiind nevoit sa gaseasca un drum mai lung?

Da.*/
//Dijkstra clasic O(N^2)
#include<fstream>
using namespace std;
#define inf 320000
#define nmax 51
#define KMAX 10001
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
int i, j, minim, k, ok, n, C[nmax][nmax], L[nmax][nmax], s, p, m, nr, w=KMAX;
int viz[nmax], d[nmax], tata[nmax], baze[nmax];
void citire()
{f>>n>>m;
 for(int i=1;i<=n;i++)
	 for(int j=1;j<=n;j++) {C[i][j]=inf; if(i==j) C[i][j]=0;} 
 int x,y,z;
 for(int i=1;i<=m;i++){f>>x>>y>>z; C[x][y]=C[y][x]=z;}
 }
 void drum ()
 {int x=n;
  g<<"\n";
  while(tata[x]) 
    {nr+=L[x][tata[x]];
     if(baze[x]==1) {if(nr<w) w=nr; nr=0;}
	 x=tata[x];
	 g<<w<<" ";
     }
 }
void dijkstra()
{ for (i = 1; i<=n; i++) {d[i] = C[1][i];tata[i] = 1;}
    
 tata[1] = 0;
 viz[1] = 1; ok = 1; int poz=0;
 while (ok) 
   {minim = inf;
    for (i = 1; i<=n; i++)
            if (!viz[i] && minim>d[i]) 
			   {minim = d[i];
				poz = i;
			   }
	if (minim!=inf) 
			{viz[poz] = 1;
             for (i = 1; i<=n; i++)
                 if (viz[i]==0 && d[i]>d[poz]+C[poz][i]) 
				     {d[i] = d[poz]+C[poz][i];
                      tata[i] = poz;
					 }
            }
            else ok = 0;
    }
 
}
int main()
{citire();f.close();
 dijkstra();
 for(int i=2;i<=n;i++) g<<d[i]<<" ";
 g<<"\n";
 //g<<dijkstra()<<" ";
 //drum();
 //g<<w<<"\n";
 g.close();
 return 0;
}