#include<cstdio>
#include<fstream>
#include<vector>
#include<utility>
#define NMAX 50010
#define oo 999999999
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
vector<pair<int,int> >V[50010];
void read(),solve(),HeapUp(int),HeapDown();
int a,b,c,m,n,curr,H[NMAX],cost[NMAX],poz[NMAX],i,nn;
int main()
{
    read();
    solve();
    return 0;
}
void read()
{
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    f>>n>>m;
    for(;m;m--)
    {
        f>>a>>b>>c;
        V[a].push_back(make_pair(b,c));
    }
}
void solve()
{
    for(i=1;i<=n;i++){H[i]=i;cost[i]=oo;poz[i]=i;}
    cost[1]=0;
    for(nn=n;nn;)
    {
        curr=H[1];
        for(vector<pair<int,int> >::iterator it=V[curr].begin();it!=V[curr].end();it++)
        {   
            if(cost[it->first]>cost[curr]+it->second)
            {
                cost[it->first]=cost[curr]+it->second;
                HeapUp(it->first); //hip-hop:)))))))))
            }
        }
        poz[H[nn]]=1;
        H[1]=H[nn];
        --nn;
        HeapDown();
    }
    for(i=2;i<=n;i++)if(cost[i]==oo)g<<"0 "; else g<<cost[i]<<" ";
}
void HeapUp(int X)
{
    int aux,cn;
    for(int cnt=poz[X];cnt>1;)
    {
        cn=cnt>>1;
        if(cost[H[cnt]]<cost[H[cn]])
        {
            poz[H[cn]]=cnt;
            poz[H[cnt]]=cn;
            aux=H[cnt];
            H[cnt]=H[cn];
            H[cn]=aux;
            cnt=cn;
            continue;
        }
        return;
    }
}
void HeapDown()
{
    int aux,cn;
    for(int cnt=1;;)
    {
        cn=cnt<<1;
        if(cn>nn)return;
        if(cn<nn)
            if(cost[H[cn+1]]<cost[H[cn]])++cn;
        if(cost[H[cnt]]<=cost[H[cn]])return;
        aux=H[cnt];H[cnt]=H[cn];H[cn]=aux;
        poz[H[cnt]]=cnt;poz[H[cn]]=cn;
        cnt=cn;
    }
}