#include <fstream>
#include <vector>
#include <queue>
#define PII pair<int,int>
#define PB push_back
#define MP make_pair
#define st first
#define nd second
 
using namespace std;
 
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
 
const int INF = 0x3f3f3f3f , MAXN = 50001;
vector<PII> G[MAXN];
int D[MAXN] ,  N , M , nod;
 
 
void read_data()
{
    fin>>N>>M;
    for(int x,y,c;M;M--)
        fin>>x>>y>>c , G[x].PB(MP(c,y));
}
 
void Bellman()
{
    bool ok[MAXN];
    queue<int> Q;
    memset(ok,false,sizeof(ok));
    memset(D,INF,sizeof(D));
    D[1] = 0;
    ok[1] = true;
    Q.push(1);
    while(!Q.empty())
    {
        nod = Q.front() , Q.pop();
        ok[nod] = false;
        for(int i=0;i<(int)G[nod].size();++i)
            if(G[nod][i].st + D[nod] < D[G[nod][i].nd])
            {
                 D[G[nod][i].nd] = G[nod][i].st + D[nod];
                 if(!ok[G[nod][i].nd])
                     ok[G[nod][i].nd] = true , Q.push(G[nod][i].nd);
            }
    }
}
 
void write_data()
{
    for(int i=2;i<=N;++i)
        D[i]==INF ? fout<<"0 " : fout<<D[i]<<' ';
}
 
 
int main()
{
    read_data();
    Bellman();
    write_data();
    return 0;
}