#include<cstdio>
#include<vector>
#include<set>
using namespace std;
struct sp
{
    int y,co;
};
int co[50005];
struct innt
{
    int y;
    const bool operator <(const innt & other) const
    {
        if(co[y]!=co[other.y])
        return co[y]<co[other.y];
        return y<other.y;
    }
};
vector<sp> ve[50005];
set<innt> hp;
bool ins[50005];
int main()
{
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    int n,m,i,x,lm;
    sp tm;
    innt tn,tp;
    set<innt> :: iterator it;
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;i++)
    {
        scanf("%d%d%d",&x,&tm.y,&tm.co);
        ve[x].push_back(tm);
    }
    lm=600000000;
    for(i=2;i<=n;i++)
        co[i]=lm;
        co[1]=0;
    tn.y=1;
    hp.insert(tn);
    while(!hp.empty())
    {
        it=hp.begin();
        tn=*it;
     //   printf("o:%d %d\n",tn.y,co[tn.y]);
        hp.erase(it);
        if(ins[tn.y]==0)
        {
        ins[tn.y]=1;
        for(i=ve[tn.y].size()-1;i>=0;i--)
        {
        if(co[ve[tn.y][i].y]>co[tn.y]+ve[tn.y][i].co)
        {
    co[ve[tn.y][i].y]=co[tn.y]+ve[tn.y][i].co;
    tp.y=ve[tn.y][i].y;
    //   printf("i:%d %d\n",tp.y,co[tp.y]);
    hp.insert(tp);
        }
        }
        }
    }
    for(i=2;i<=n;i++)
        if(co[i]<lm)
        printf("%d ",co[i]);
        else
        printf("0 ");
    return 0;
}