#include <cstdio>
#include <set>
#include <vector>
#define mp make_pair
#define pb push_back
#define INF 99999999
using namespace std;
vector <pair< int,int> > g[5100];
int cost[5100],x,y,c,n,m,i;
void dijkstra()
{
    vector <pair<int,int> > :: iterator it;
    set <pair<int,int> > v;
    v.insert(mp(0,1));
    while(!v.empty())
    {
       int nod=(*v.begin()).second;
       int cc=(*v.begin()).first;
        for(it=g[nod].begin();it!=g[nod].end();++it)
        {
            if(cost[(*it).second]>cc+(*it).first)
                {
                    cost[(*it).second]=cc+(*it).first;
                    v.insert(mp(cc+(*it).first,(*it).second));
                }
        }
         v.erase(v.begin());

    }
}
int main()
{
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    scanf("%d %d",&n,&m);
    for(i=1;i<=m;++i)
    {
        scanf("%d %d %d",&x,&y,&c);
        g[x].push_back(make_pair(c,y));
    }
    for(i=1;i<=n;++i) cost[i]=INF;
    cost[1]=0;
    dijkstra();
    for(i=2;i<=n;++i)
    {
        if(cost[i]!=INF) printf("%d ",cost[i]);
        else printf("0 ");
    }
    return 0;
}