#include<stdio.h>
#include<queue>
#include<vector>
#define INF 10000001
#define Nmx 50005
#define mp make_pair
#define pb push_back

using namespace std;

vector< pair<int,int> > G[Nmx];
int n,m,cost[Nmx],viz[Nmx];
struct cmp
{
	bool operator () (const int &a,const int &b) const
	{
		return cost[a]>cost[b];
	}
};
priority_queue < int , vector< int > , cmp > Q;

void citire()
{
    scanf("%d%d",&n,&m);
    int x,y,c;
    for(int i=1;i<=m;++i)
    {
        scanf("%d%d%d",&x,&y,&c);
        G[x].pb(mp(y,c));
    }
}

void dijkstra()
{
    vector< pair<int,int> > ::iterator it;
    for(int i=2;i<=n;++i)
        cost[i]=INF;
    Q.push(1);
    while(!Q.empty())
    {
        int nod=Q.top();
        Q.pop();
        viz[nod]=0;
        for(it=G[nod].begin();it!=G[nod].end();++it)
            if(cost[it->first]>cost[nod]+it->second)
            {
                cost[it->first]=cost[nod]+it->second;
                if(!viz[it->first])
                {
                    viz[it->first]=1;
                    Q.push(it->first);
                }
            }
    }
    for(int i=2;i<=n;++i)
        printf("%d ",cost[i]);
    printf("\n");
}
int main()
{
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    citire();
    dijkstra();
    return 0;
}