#include <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
#include <set>

#define N 50001
#define INF 1<<29
using namespace std;

struct per{
           int node,cost;
          };
vector <per> G[N];
int n,d[N];

void Read(){

    int i,m,x,y,cost;
    per p;
    freopen("dijkstra.in","r",stdin);

    scanf("%d%d",&n,&m);
    while (m--){
        scanf("%d%d%d",&x,&y,&cost);
        p.node=y;p.cost=cost;
        G[x].push_back(p);
        }

}

void Dijkstra(){

    set< pair<int,int> > H;
    int u,v,cost;

    for (int i=2;i<=n;++i) d[i]=INF;
    H.insert(make_pair(0,1));

    while (!H.empty())
    {
        u=H.begin()->second;
        H.erase(H.begin());

        for (int i=0;i<G[u].size();++i)
        {
            v=G[u][i].node;
            cost=G[u][i].cost;
            if (d[v]>d[u]+cost)
            {

                if (d[v]!=INF) H.erase(H.find(make_pair(d[v],v)));
                d[v]=d[u]+cost;
                H.insert(make_pair(d[v],v));
            }
        }
    }
}

void Write(){

    int i;
    freopen("dijkstra.out","w",stdout);

    for (i=2;i<=n;++i)
        if (d[i]!=INF) printf("%d ",d[i]);
        else printf("0 ");
}

int main()
{
    Read();
    Dijkstra();
    Write();
    return 0;
}