#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_pair

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

vector<pair<int,int> > G[NM];
struct queuew
{
    int a[NM];
    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;

int main()
{
    char isin[NM];

    //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;

    memset(isin,0,sizeof(isin));

    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;

         for(int i=0;i<(int)G[nod].size();++i)
         {
              #define nnod G[nod][i].first
              #define ncost G[nod][i].second

              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;
}