#include<fstream>
#include<vector>
#include<queue>
using namespace std;
#define NMAX 50001
#define inf 0x3fffff
int n,m,aux;
struct graf{int nod,cost;} e;
vector <graf> a[NMAX];
vector <int> d(NMAX,inf);
queue<int> Q;
void cit(),dijkstra(),scrie();
int main()
{cit(); dijkstra(); scrie(); return 0;}
void cit()
{ifstream f("dijkstra.in"); f>>n>>m;
 for(register int x,y,z,i=1;i<=m;++i) f>>x>>y>>z,e.nod=y,e.cost=z,a[x].push_back(e);
 f.close();
}
void dijkstra()
{Q.push(1);d[1]=0;  
 while(!Q.empty())
	{
	 aux=Q.front();Q.pop();
	 for(unsigned int i=0;i<a[aux].size();++i) 
		{int wcost=a[aux][i].cost,wnod=a[aux][i].nod;
	     if(d[wnod]>d[aux]+wcost) {d[wnod]=d[aux]+wcost; Q.push(wnod);}
		}
	}
}
void scrie()
{ofstream g("dijkstra.out");
 for(register int i=2;i<=n;++i) g<<(d[i]==inf?0:d[i])<<' '; g<<'\n'; g.close(); 
}