#include<fstream>
#include<string>
#include<vector>
#include<queue>
#include<algorithm>

using namespace std;

#define NM 50005
#define inf 2000000000
#define PB push_back
#define MKP make_pair2

int N,M,S,COST[NM],FAT[NM];

vector<pair<int,int> > G[NM];

pair<int,int> make_pair2(int a,int b)
{
    pair<int,int> ret(a,b);
    return ret;
}

struct queuew
{
    int a[NM*2];
    int st,dr;
    
    queuew()
    {
        st = 0;
        dr = 0;
    }

    void push(int ceva)
    {
        a[++dr] = ceva;
    }
    
    int size()
    {
        return dr-st;
    }
    
    int front()
    {
        return a[st+1];
    }
    
    int pop()
    {
        return a[++st];
    }

    bool empty()
    {
        return st >= dr;
    }
} Q;

char isin[NM];


int main()
{

    //int start=clock();

    int a,b,c;

    //freopen("dijkstra.in","r",stdin);
    //freopen("dijkstra.out","w",stdout);
    ifstream fin("dijkstra.in");
    ofstream fout("dijkstra.out");

    //scanf("%d %d",&N,&M,&S);
    
    fin >> N >> M;

    S=1;

    for(int i=1;i<=M;++i)
    {
        //scanf("%d %d %d",&a,&b,&c);
        fin >> a >> b >> c;
        G[a].PB(MKP(b,c));
    }

    for(int i=1;i<=N;++i)
       COST[i]=inf;

    COST[S]=0;
    Q.push(S);
    isin[S]=1;

    while(!Q.empty())
    {
         int nod=Q.front();
         Q.pop();
         isin[nod]=0;

         if(isin[FAT[nod]]) continue;

          #define nnod G[nod][i].first
          #define ncost G[nod][i].second


         for(int i=0;i<(int)G[nod].size();++i)
          if(COST[nnod]>COST[nod]+ncost)
          {
              COST[nnod]=COST[nod]+ncost;
              FAT[nnod]=FAT[nod];
              if(!isin[nnod])
              {
                   Q.push(nnod);
                   isin[nnod]=1;
              }
          }
    }

    for(int i=2;i<=N;++i)
       if(COST[i]==inf) //printf("0 ");
            fout << "0 ";
       else //printf("%d ",COST[i]);
            fout << COST[i] << " ";

    fout.close();

    //int stop=clock();

    //printf("\n%lf",(double)(stop-start)/CLOCKS_PER_SEC);

    return 0;
}