#include <fstream>
#include <cstdio>
#include <vector>
#include <set>

using namespace std;

const int N=100001;
const int M=250001;
const int INF=1<<30;
const int PARS=10000;

vector < pair <int,int> > edge[N];
set < pair <int,int> > map;


int cost[N],n,m;
char buff[PARS];
int pozitie=PARS-1;

void citire(int &nr){
    nr=0;
    while(buff[pozitie]<'0' || buff[pozitie]>'9')
        if (++pozitie==PARS){
            fread (buff,1,PARS,stdin);
            pozitie=0;
        }
    while('0'<=buff[pozitie] && buff[pozitie]<='9'){
        nr=nr*10+buff[pozitie]-'0';
        if (++pozitie==PARS){
            fread (buff,1,PARS,stdin);
            pozitie=0;
        }
     }
}

void Dijkstra(){
	int i,costaux,nod;
	for(i=2;i<=n;++i){
		cost[i]=INF;
	}
	set< pair <int,int> >::iterator it;
	map.insert(make_pair(0,1));
	while(!map.empty()){
		it=map.begin();
		costaux=(*it).first;
		nod=(*it).second;
		map.erase(it);
		for(i=0;i<edge[nod].size();++i){
			if(costaux+edge[nod][i].second<cost[edge[nod][i].first]){
				cost[edge[nod][i].first]=costaux+edge[nod][i].second;
				map.insert(make_pair(cost[edge[nod][i].first],edge[nod][i].first));
			}
		}
	}
}

void read(){
	int a,b,c;
	freopen("dijkstra.in","r",stdin);
	citire(n);
	citire(m);
	for(int i=1;i<=m;i++){
		citire(a);
		citire(b);
		citire(c);
		edge[a].push_back(make_pair(b,c));
	}
}

void write(){
	freopen("dijkstra.out","w",stdout);
	for(int i=2;i<=n;++i){
		if(cost[i]==INF){
			printf("0 ");
			continue;
		}
		printf("%d ",cost[i]);
	}
}

int main(){
	read();
	Dijkstra();
	write();
	return 0;
}