#include <cstdio>
#include <vector>
#include <queue>
#define NMAX 50001
#define INF 1000000000




using namespace std;

int n,x0;
vector < pair<int,int> > G[NMAX];
int dmin[NMAX];


class cmp
{
    public:
       bool operator()(const int &x, const int &y)
       {
           return dmin[x]>dmin[y];
       }
};

priority_queue <int, vector<int>,cmp> Q;

void citire()
{
    int m,x,y,c;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&x,&y,&c);
        G[x].push_back(make_pair(y,c));
    }
}

void dijkstra()
{
    for(int i=1;i<=n;i++)
      dmin[i]=INF;
    dmin[1]=0;
    Q.push(1);
    while(!Q.empty())
    {
        int vf=Q.top();
        Q.pop();
        for(int i=0;i<G[vf].size();i++)
           if(dmin[G[vf][i].first]>dmin[vf]+G[vf][i].second)
               {
                  dmin[G[vf][i].first]=dmin[vf]+G[vf][i].second;
                  Q.push(G[vf][i].first);
               }
    }
}

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

int main()
{
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    citire();
    dijkstra();
    afisare();
    return 0;
}