#include <cstdio>
#include <vector>
#include <utility>
#define N 50005
using namespace std;
vector< pair< int, int> > v[N];
int n,m,i,d[N],h[N],p[N],L,a,b,c,oo=50000010,nod,cost;
void sw(int,int),HU(int),HD(int);
int main()
{
    freopen("dijstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    scanf("%d%d",&n,&m);
    for(;m;m--)
    {
        scanf("%d%d%d",&a,&b,&c);
        v[a].push_back(make_pair(b,c));
    }
    for(i=1;i<=n;i++){d[i]=oo;h[i]=p[i]=i;}
    d[1]=0;L=n;
    for(;L&&d[1]!=oo;)
    {
        nod=h[1];cost=d[nod];
        sw(1,L);L--;HD(1);
        for(vector<pair<int,int> > ::iterator it=v[nod].begin();it!=v[nod].end();it++)
            if(p[it->first]<=L)
                if(d[it->first]>cost+it->second)
                {
                    d[it->first]=cost+it->second;
                    HU(p[it->first]);
                }
    }
    for(i=2;i<=n;i++)
        d[i]==oo?printf("0 "):printf("%d ",d[i]);
    return 0;
}
void sw(int i,int j)
{
    int aux=h[i];h[i]=h[j];h[j]=aux;
    p[h[i]]=i;p[h[j]]=j;
}
void HU(int fiu)
{
    int tata=fiu>>1;
    if(!tata)return;
    if(d[h[fiu]]<d[h[tata]]){sw(tata,fiu);HU(tata);}
}
void HD(int tata)
{
    int fiu=tata<<1;
    if(fiu>L)return;
    if(fiu<L&&d[h[fiu]]>d[h[fiu+1]])fiu++;
    if(d[h[fiu]]<d[h[tata]]){sw(tata,fiu);HD(fiu);}
}